S04-02 集合框架-Collection

• Collection~
  • 体系架构
  • 核心原理
  • API：Collection
    • 元素添加与扩充
    • 元素删除与清理
    • 状态查询与校验
    • 数据转换与迭代
  • 注意事项
  • 实战：敏感词过滤系统
• List~
  • 接口定义与体系结构
  • 核心特性
  • 核心实现类
  • 核心实现类原理
    • ArrayList 核心原理
    • LinkedList 核心原理
  • API：List
    • 静态工厂创建
    • 增删改查
    • 搜索、排序与截取
    • 注意事项
  • 实战：待办任务管理器
• List-ArrayList~
  • 底层数据结构
  • 动态扩容
  • 随机访问
  • 线程不安全
  • Fail-Fast 机制
  • API：ArrayList
    • 构造与空间优化
    • 元素增删改查
    • 状态检索与遍历
  • 实战：学生信息库管理系统
• List-LinkedList~
  • 双向链表实现
  • 时间复杂度
  • 使用场景
  • API：LinkedList
    • 构造方法
    • 列表核心操作
    • 双端队列与栈操作
  • 注意事项
  • 实战：双端队列应用
• List-Vector~
  • 体系架构
  • 核心原理
  • API：Vector
    • 构造与容量控制
    • 遗留专属操作
  • 注意事项
  • 实战：高并发全链路应用日志异步收集器
• Set~
  • 核心原理
  • 核心特性
  • 核心实现类
  • API：Set
    • 基础操作
    • 集合运算
• Set-HashSet~
  • 核心特性
  • 底层是 HashMap
  • 扩容与性能调优
  • 哈希碰撞与去重机制@
  • API：HashSet
    • 构造方法
    • 基本操作
  • 注意事项
  • 实战：用户行为日志分析
• Set-HashSet-LinkedHashSet~
  • 核心特性
  • 底层数据结构
  • API：LinkedHashSet
    • 构造方法
    • 基本操作
  • 注意事项
  • 实战：用户浏览记录管理
• Set-TreeSet~
  • 核心特性
  • 底层数据结构
  • 节点寻址与平衡控制
  • 排序和去重机制@
    • 排序机制
    • 去重机制
    • compareTo vs equals
  • API：TreeSet
    • 构造方法
    • 导航与区间检索
  • 注意事项
  • 技术选型
  • 实战：股票实时价格监控
• Queue~
  • 概述与体系结构
  • 核心原理与方法体系
  • API：Queue
    • 插入操作组
    • 移除操作组
    • 检查操作组
  • 注意事项
  • 实战案例：订单排队处理系统
• Queue-PriorityQueue~
  • 概述与体系结构
  • 核心原理
    • 堆的数组映射规则
    • 算法时间复杂度
  • API：PriorityQueue
    • 构造方法组
    • 核心操作组
  • 注意事项
  • 实战案例：医院急诊分诊系统
• Deque~
  • 概述与体系结构
  • 核心原理与方法体系
  • 方法对照矩阵
  • API：Deque
    • 队首操作组
    • 队尾操作组
    • 栈操作等价组
  • 注意事项
  • 实战：文本编辑器管理器
• DeQue-ArrayDeque
  • 概述与体系结构
  • 核心原理
    • 循环双端缓冲区实现
    • 算法时间复杂度
  • API：ArrayDeque
    • 构造方法组
    • 队首操作组
    • 队尾操作组
    • 栈操作等价组
  • 注意事项
  • 实战：浏览器历史记录导航

[TOC]

Collection~

体系架构

体系架构:

java.util.Collection 是 Java 集合框架（Java Collection Framework） 根接口之一，它定义了单列集合的核心公用规范。所有的单列集合实现类（如 ArrayList、HashSet、LinkedList 等）都间接或直接继承自该接口。通过高层抽象，Collection 屏蔽了底层数据结构的差异性，为上层业务提供了统一的元素操作边界。

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;

public class CollectionArchitectureDemo {
  public static void main(String[] args) {
    // 使用 Collection 接口引用指向不同的子类实现，体现多态架构
    Collection<String> listCollection = new ArrayList<>();
    Collection<String> setCollection = new HashSet<>();

    listCollection.add("Element 1");
    setCollection.add("Element 1");

    System.out.println("List Collection: " + listCollection);
    System.out.println("Set Collection: " + setCollection);
  }
}

核心原理

核心原理:

Collection 接口的设计依赖于两个核心机制：迭代器模式（Iterator Pattern） 与 基础存取契约。

1. 写时复制与快速失败（Fail-Fast）：底层数据结构在发生并发变更或在迭代过程中被非迭代器方法修改时，会通过内部的 modCount 计数器检测并立即抛出 ConcurrentModificationException。

2. 元素引用存储：Java 集合仅存储对象的引用地址，而非对象本身。

3. 等值性判定规范：依赖于 Object.equals(Object obj) 和 Object.hashCode() 规范。任何向集合存取数据的操作（如 contains、remove），其底层正确性完全取决于该元素类是否正确重写了等值判定方法。

   import java.util.ArrayList;
   import java.util.Collection;
   import java.util.Iterator;
   import java.util.ConcurrentModificationException;
   
   public class FailFastMechanismDemo {
     public static void main(String[] args) {
       Collection<String> collection = new ArrayList<>();
       collection.add("Java");
       collection.add("Go");
       collection.add("Rust");
   
       try {
         Iterator<String> iterator = collection.iterator();
         while (iterator.hasNext()) {
           String element = iterator.next();
           if ("Go".equals(element)) {
             // 触发现实异常：在迭代过程中直接通过集合的 remove 方法修改结构
             collection.remove(element);
           }
         }
       } catch (ConcurrentModificationException e) {
         System.out.println("成功捕获并验证 Fail-Fast 异常: " + e.toString());
       }
     }
   }

API：Collection

元素添加与扩充

元素添加与扩充:

• boolean add()：(E e)，向集合中追加指定的元素。若集合因调用而发生改变则返回 true；若集合拒绝重复元素（如 Set）且元素已存在，则返回 false。

• boolean addAll()：(Collection<? extends E> c)，将指定集合中的所有元素批量添加到当前集合中。只要当前集合结构发生改变，即返回 true。

  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashSet;
  
  public class AddApiDemo {
    public static void main(String[] args) {
      Collection<Integer> mainCollection = new ArrayList<>();
      boolean isAdded = mainCollection.add(100); // 注入单元素
  
      Collection<Integer> sourceCollection = new HashSet<>();
      sourceCollection.add(200);
      sourceCollection.add(300);
  
      boolean isBatchAdded = mainCollection.addAll(sourceCollection); // 注入批数据
  
      System.out.println("单元素添加状态: " + isAdded);
      System.out.println("批元素添加状态: " + isBatchAdded);
      System.out.println("最终集合内容: " + mainCollection);
    }
  }

元素删除与清理

元素删除与清理:

• boolean remove()：(Object o)，从此集合中移除指定元素的单个实例（若存在）。成功移除返回 true。

• boolean removeAll()：(Collection<?> c)，移除当前集合中包含在指定集合中的所有元素（求差集）。

• boolean removeIf()：(Predicate<? super E> filter)，J8+，根据给定的断言条件函数式过滤元素，满足条件的元素将被移除。

• boolean retainAll()：(Collection<?> c)，仅保留当前集合中那些包含在指定集合中的元素（求交集）。若当前集合结构因该操作发生改变（即移除了某些元素），则返回 true。

• void clear()：()，清空当前集合中的所有元素，释放引用。

  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.List;
  
  public class RemoveApiDemo {
    public static void main(String[] args) {
      Collection<String> languages = new ArrayList<>(List.of("Java", "Python", "C++", "JavaScript"));
  
      languages.remove("C++"); // 条件删除单实例
      languages.removeIf(lang -> lang.startsWith("Java")); // 函数式断言过滤
  
      System.out.println("过滤后的集合: " + languages);
  
      languages.clear(); // 强制清空
      System.out.println("清空后的集合状态，大小为: " + languages.size());
  
      Collection<String> activeRoutes = new ArrayList<>(List.of("RouteA", "RouteB", "RouteC"));
      Collection<String> standardRoutes = List.of("RouteB", "RouteC", "RouteD");
      // 执行交集计算，仅保留同时存在于两个集合中的标准路由
      boolean isModified = activeRoutes.retainAll(standardRoutes);
    }
  }

状态查询与校验

状态查询与校验:

• int size()：()，返回当前集合中的元素数量。若元素数量超过 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。

• boolean isEmpty()：()，校验当前集合是否不包含任何元素。当且仅当 size() == 0 时返回 true。

• boolean contains()：(Object o)，判断当前集合是否包含指定的元素。底层执行 (o==null ? e==null : o.equals(e)) 的匹配检索。

• boolean containsAll()：(Collection<?> c)，检查当前集合是否包含指定集合中的所有元素（即包含包含关系，求子集判定）。

• boolean equals()：(Object o)，比较指定对象与当前集合是否相等。在多态体系下，通常规范要求在线性表（List）之间、散列表（Set）之间各自定义严格的对等比较规则。

  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.List;
  
  public class QueryApiDemo {
    public static void main(String[] args) {
      Collection<String> target = new ArrayList<>(List.of("A", "B", "C"));
  
      System.out.println("集合是否为空: " + target.isEmpty());
      System.out.println("集合元素尺寸: " + target.size());
      System.out.println("是否包含元素 'B': " + target.contains("B"));
      System.out.println("是否全包含 ['A', 'C']: " + target.containsAll(List.of("A", "C")));
  
      HashSet set1 = new HashSet(Set.of(1, 2, 3));
      HashSet set2 = new HashSet(Set.of(3, 2, 1));
      System.out.println("set1 = set1? " + set1.equals(set2)); // true
  
      ArrayList<Integer> list1 = new ArrayList<>(List.of(10, 20, 30));
      ArrayList<Integer> list2 = new ArrayList<>(List.of(30, 20, 10));
      System.out.println("list1 = list2 ? " + list1.equals(list2)); // false
    }
  }

数据转换与迭代

数据转换与迭代:

• Iterator<E> iterator()：()，获取该集合对应的高级迭代器实例，用于顺序消费、安全剔除数据。

• Object[] toArray()：()，返回一个包含此集合中所有元素的新数组。数组类型固定为 Object[]。

• <T> T[] toArray()：(T[] a)，返回包含此集合所有元素的指定类型数组。若传入的数组空间充足，则复用该数组；若不足，则通过反射重新构建合适尺寸的同类型数组。

• int hashCode()：()，返回当前集合的哈希码值。集合的哈希码计算依赖于其内部元素，必须与 equals 方法保持一致性契约。

  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.List;
  
  public class TransformApiDemo {
    public static void main(String[] args) {
      Collection<String> fruits = new ArrayList<>(List.of("Apple", "Banana"));
  
      // 1. 转换为基础 Object 数组
      Object[] objectArray = fruits.toArray();
  
      // 2. 转换为指定类型的强类型数组
      String[] stringArray = fruits.toArray(new String[0]);
  
      System.out.println("强类型数组长度: " + stringArray.length + ", 首元素: " + stringArray[0]);
  
      // 3. 哈希码值
      System.out.println(fruits.hashCode()) // -1959803623
    }
  }

注意事项

注意事项:

1. UnsupportedOperationException 风险：

   通过 List.of()、Arrays.asList() 或 Collections.unmodifiableCollection() 生成的集合对象，底层多为只读或固定长度的视图类实现。对其调用 add() 或 remove() 等结构性变更方法将抛出此运行时异常。

   public class D06_UnsupportedOperationException {
     public static void main(String[] args) {
       List<Integer> list1 = List.of(1, 2, 3);
       List<Integer> list2 = Arrays.asList(10, 20, 30);
   
       // 增删操作
       // list1.add(4); // UnsupportedOperationException
       // list2.add(40); // UnsupportedOperationException
   
       list1.remove(3); // UnsupportedOperationException
       list2.remove(30); // UnsupportedOperationException
   
       System.out.println("list1 = " + list1);
       System.out.println("list2 = " + list2);
     }
   }

2. 元素重写风险：

   当 Collection 具体的实现子类为 HashSet 时，若存入自定义对象却未同时正确重写 equals() 与 hashCode() 方法，会导致 contains() 失效以及内存泄漏（无法检索旧引用重复覆盖）。

   public class CustomObjectOverride {
     public static void main(String[] args) {
       // 没有重写 equals 和 hashCode
       Person p1 = new Person("Tom", 18);
       Person p2 = new Person("Tom", 18);
   
       // 重写了 equals 和 hashCode
       PersonOverride p3 = new PersonOverride("Tom", 18);
       PersonOverride p4 = new PersonOverride("Tom", 18);
   
       // 对比
       System.out.println("p1.equals(p2) = " + p1.equals(p2)); // false
       System.out.println("p3.equals(p4) = " + p3.equals(p4)); // true
     }
   }

3. 多线程并发安全风险：

   java.util.Collection 的基础实现类（如 ArrayList, HashSet）皆是非线程安全的。在多线程环境中存在竞态条件，需替换为 java.util.concurrent 包下的并发容器，或使用 Collections.synchronizedCollection() 进行包装。

实战：敏感词过滤系统

以下案例模拟了一个线上商城的敏感词汇过滤系统。它接收基础输入，并利用 Collection 的标准接口规范实现批量导入、动态条件清洗以及强类型转换输出的全闭环流程。

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class SensitiveWordFilterSystem {

  /**
     * 核心业务处理方法：清洗并标准化敏感词集合
     */
  public static String[] processSensitiveWords(Collection<String> inputSource) {
    // 容错处理：确保输入集合非空
    if (inputSource == null || inputSource.isEmpty()) {
      return new String[0];
    }

    // 1. 利用高层接口进行多态构建新容器，避免破坏原入参数据
    Collection<String> wordRepository = new ArrayList<>(inputSource);

    // 2. 注入固定基础屏蔽词组件
    Collection<String> baseBlacklist = List.of("illegal", "malware", "hack");
    wordRepository.addAll(baseBlacklist);

    // 3. 业务数据清洗：去除无意义空白符、统一转换为小写
    Collection<String> sanitizedRepository = new ArrayList<>();
    for (String word : wordRepository) {
      if (word != null) {
        sanitizedRepository.add(word.trim().toLowerCase());
      }
    }

    // 4. 应用函数式条件断言过滤：剔除所有长度小于 3 字符或超过 20 字符的无效词条
    sanitizedRepository.removeIf(word -> word.length() < 3 || word.length() > 20);

    // 5. 校验清洗后的集合状态并输出强类型数据数组
    if (sanitizedRepository.contains("malware")) {
      System.out.println("[系统核心提示]：内置关键敏感词已成功加载。");
    }

    // 将清洗完的 Collection 统一转换为严谨的强类型 String 数组输出
    return sanitizedRepository.toArray(new String[0]);
  }

  public static void main(String[] args) {
    // 模拟外部输入的原始脏词汇集合
    Collection<String> dirtyInputs = new ArrayList<>();
    dirtyInputs.add("  Bitcoin  ");
    dirtyInputs.add("ab"); // 长度过短，预期被过滤
    dirtyInputs.add("SPAM_KEYWORDS_LONG_TEXT_TEST_FAILED"); // 长度过长，预期被过滤
    dirtyInputs.add("Phishing");

    System.out.println("--- 系统准备启动，正在执行原始词汇清洗 ---");
    String[] finalBlacklist = processSensitiveWords(dirtyInputs);

    System.out.println("\n--- 清洗完毕，系统最终生效的合规敏感词列表如下：---");
    for (String node : finalBlacklist) {
      System.out.println("有效敏感词项: [" + node + "]");
    }
  }
}

List~

接口定义与体系结构

接口定义与体系结构:

java.util.List 是 Java 集合框架的核心根接口之一，它继承自 java.util.Collection 接口。List 代表一个有序的、允许元素重复的线性集合。用户可以通过整数索引（位置）精确控制每个元素的插入位置，并能通过索引访问、修改和删除元素。

注意事项：

1. List 集合的索引从 0 开始，最大索引值为 size() - 1。
2. 访问不存在的索引会抛出 IndexOutOfBoundsException 运行时异常。
3. 部分实现类允许存放 null 值，但过度依赖 null 容易埋下 NullPointerException 的隐患。

import java.util.ArrayList;
import java.util.List;

public class ListArchitectureDemo {
  public static void main(String[] args) {
    // 实例化一个实现类并向上转型为 List 接口
    List<String> sequence = new ArrayList<>();

    // 验证有序性与可重复性
    sequence.add("ElementA");
    sequence.add("ElementB");
    sequence.add("ElementA"); // 允许重复值

    System.out.println("集合内容: " + sequence);
    System.out.println("集合长度: " + sequence.size());
  }
}

核心特性

List 接口之所以独特，主要是因为它具备以下三大核心特征：

• 精确有序（Ordered）： 元素进入集合的顺序会被严格保留。先添加的在前面，后添加的在后面。
• 带有索引（Index-based）： 每个元素都有其对应的整数索引位置（从 0 开始到 size() - 1），你可以像操作数组一样，直接通过索引来获取或修改元素。
• 允许重复（Allow Duplicates）： 集合中可以存在多个完全相同的元素，也可以包含多个 null 值。

核心实现类

核心实现类：

List 是一个接口，不能直接实例化。在实际开发中，我们主要使用以下三个实现类：

1. ArrayList（动态数组）：

   底层基于可变大小的数组实现。它是开发中最常用的默认实现。

   • 优点： 随机访问（通过索引获取元素）性能极高，时间复杂度为 O(1)。
   • 缺点： 中间插入或删除元素涉及数组元素的整体移动，性能较慢，时间复杂度为 O(n)。

2. LinkedList（双向链表）：

   底层基于双向链表数据结构实现，每个节点都保存了上一个和下一个节点的引用。

   • 优点： 在已知位置进行插入和删除操作时非常快，只需要修改指针，时间复杂度为 O(1)。
   • 缺点： 不支持高效的随机访问，查找元素必须从头或从尾开始遍历，时间复杂度为 O(n)。

3. Vector（古老的线程安全数组）：

   底层同样基于数组，是 Java 1.0 的产物。

   • 特点： 它的所有核心方法都加了 synchronized 关键字，因此是线程安全的。
   • 现状： 它的效率非常低，在现代 Java 开发中已被废弃。如果需要线程安全的 List，通常会使用 java.util.concurrent.CopyOnWriteArrayList 或通过 Collections.synchronizedList() 进行包装。

三者全方位对比表：

特性	ArrayList	LinkedList	Vector
底层数据结构	动态数组	双向链表	动态数组
线程安全	否	否	是
随机访问 get(i)	极快 O(1)	较慢 O(n)	快 O(1)
尾部插入 add()	快（除非触发扩容）	快 O(1)	快
中间插入/删除	较慢 O(n)	较快 O(1)（若已定位）	较慢 O(n)
默认扩容机制	原容量的 1.5 倍	无需扩容（动态链表）	原容量的 2 倍

核心实现类原理

List 接口最常用的两个核心实现类为 ArrayList 和 LinkedList。由于底层数据结构的不同，它们在内存布局和操作的时间复杂度上存在本质差异。

ArrayList 核心原理

ArrayList 核心原理:

ArrayList 底层基于可变长对象数组（Object[] elementData）实现。

• 扩容机制：默认初始容量为 10（在首次添加元素时分配）。当数组空间不足时，触发自动扩容，新容量通常为原容量的 1.5 倍（计算公式为 newCapacity = oldCapacity + (oldCapacity >> 1)），随后通过 Arrays.copyOf() 将原数组数据复制到新数组中。
• 性能特征：支持随机访问，根据索引获取元素的时间复杂度为 $O(1)$；但在数组中间执行插入或删除操作时，需要调用 System.arraycopy() 移动后续元素，时间复杂度为 $O(n)$。

注意事项：

ArrayList 是线程不安全的。在多线程环境下若发生并发修改，可能会导致内部状态不一致或抛出 ConcurrentModificationException。

import java.util.ArrayList;
import java.util.List;

public class ArrayListPrincipleDemo {
  public static void main(String[] args) {
    // 创建指定初始容量的 ArrayList，可有效减少扩容带来的性能损耗
    List<Integer> arrayList = new ArrayList<>(15);  

    // 执行尾部单点数据插入
    arrayList.add(100);
    arrayList.add(200);

    // 随机访问
    Integer element = arrayList.get(0);
    System.out.println("ArrayList 索引 0 的元素: " + element);
  }
}

LinkedList 核心原理

LinkedList 核心原理:

LinkedList 底层基于双向链表实现。

• 节点结构：每个节点由内部类 Node 表示，包含三个属性：存放数据的 item、指向前驱节点的 prev 指针以及指向后继节点的 next 指针。

• 性能特征：不支持随机访问，按索引查找元素需要从头或尾进行遍历，时间复杂度为 $O(n)$；但在已知节点指针的情况下，执行插入或删除操作仅需修改指针指向，时间复杂度为 $O(1)$。由于每个节点需要额外存储两个指针，其内存开销通常大于 ArrayList。

  import java.util.LinkedList;
  import java.util.List;
  
  public class LinkedListPrincipleDemo {
    public static void main(String[] args) {
      List<String> linkedList = new LinkedList<>();
  
      linkedList.add("Node1");
      linkedList.add("Node2");
  
      // 顺序访问首部数据
      System.out.println("LinkedList 首个元素: " + linkedList.get(0));
    }
  }

API：List

除了继承自 Collection 的通用方法外，List 增加了一系列与索引（Index）相关的方法：

静态工厂创建

静态工厂创建:

• <E> List<E> List.of()：(E... elements)，返回一个包含指定元素的不可变列表。该列表拒绝 null 元素，且大小和内容均不可变。

• <E> List<E> List.copyOf()：(Collection<? extends E> coll)，根据已有集合返回一个不可变的强类型列表快照。若原集合本身已是不可变列表，则直接返回原引用。

• <T> List<T> Arrays.asList()：(T... a)，返回一个受指定数组支持的固定大小（Fixed-size）的列表。对列表元素的修改会直接同步到原数组，但无法执行 add 或 remove 等改变线性表长度的操作。

  import java.util.Arrays;
  import java.util.List;
  import java.util.ArrayList;
  
  public class ListFactoryDemo {
    public static void main(String[] args) {
      // 1. List.of 创建严格不可变列表
      List<String> immutableList = List.of("Java", "Rust", "Go");
      System.out.println("List.of 结果: " + immutableList);
  
      // 2. List.copyOf 生成只读快照
      List<String> source = new ArrayList<>();
      source.add("Docker");
      List<String> snapshot = List.copyOf(source);
      System.out.println("List.copyOf 快照: " + snapshot);
  
      // 3. Arrays.asList 绑定原原生数组
      String[] array = {"Alpha", "Beta"};
      List<String> fixedList = Arrays.asList(array);
      fixedList.set(0, "Omega"); // 同步修改原数组
      System.out.println("原数组首元素更新为: " + array[0]);
    }
  }

增删改查

增删改查:

• void add()：(int index, E element)，在列表的指定索引位置插入指定元素，将当前位置的元素及后续元素统一向右平移（索引加 1）。

• boolean addAll()：(int index, Collection<? extends E> c)，在指定的索引位置插入指定集合中的所有元素，后续元素向后平移。

• E remove()：(int index)，移除列表中指定索引位置的元素，将后续元素向左平移，并返回被删除的旧元素。

• E get()：(int index)，获取指定索引位置的元素。若访问底层为链表结构的实现，系统将执行折半线性搜索。

• E set()：(int index, E element)，用指定元素替换指定索引位置的元素，并返回被替换的旧元素。

  import java.util.ArrayList;
  import java.util.List;
  
  public class ListCrudDemo {
    public static void main(String[] args) {
      List sequence = new ArrayList<>();
      sequence.add("Element0");
      sequence.add("Element2");
      sequence.add(2);
  
      // 1. 指定位置插入（增）
      sequence.add(1, "Element1");
      System.out.println("插入后序列: " + sequence);
  
      // 2. 索引数据读取（查）
      String first = sequence.get(0);
      System.out.println("索引 0 处的元素: " + first);
  
      // 3. 覆盖指定位置元素（改）
      String oldVal = sequence.set(2, "Element2_Updated");
      System.out.println("被替换的值: " + oldVal + " | 新状态: " + sequence);
  
      // 4. 精确索引删除（删）
      String removedVal = sequence.remove(2); // 移除索引2位置的元素
      System.out.println("被移除的值: " + removedVal + " | 最终状态: " + sequence);
      sequence.remove(Integer.valueOf(2)); // 移除包装对象元素2
    }
  }

搜索、排序与截取

搜索、排序与截取:

• int indexOf()：(Object o)，正向检索列表中第一次出现指定元素的索引位置，若集合不包含该元素则返回 -1。

• int lastIndexOf()：(Object o)，反向检索列表中最后一次出现指定元素的索引位置，若集合不包含该元素则返回 -1。

• void sort()：(Comparator<? super E> c)，根据指定的比较器规则对当前列表进行原地降序或升序排列。

• List<E> subList()：(int fromIndex, int toIndex)，截取并返回 [fromIndex, toIndex) 区间内的非独立子视图（View）。对该视图的所有结构性操控会直接映射回母列表。

• ListIterator<E> listIterator()：(int index)，从列表的指定位置开始，返回列表专用的高级双向迭代器（支持向前与向后双向遍历及迭代中写操作）。

  import java.util.ArrayList;
  import java.util.Comparator;
  import java.util.List;
  import java.util.ListIterator;
  
  public class ListSearchSortSliceDemo {
    public static void main(String[] args) {
      List<Integer> dataset = new ArrayList<>(List.of(30, 10, 50, 10, 40));
  
      // 1. 定位搜索
      System.out.println("首次出现 10 的索引: " + dataset.indexOf(10));
      System.out.println("最后出现 10 的索引: " + dataset.lastIndexOf(10));
  
      // 2. 原地自然升序排序
      dataset.sort(Comparator.naturalOrder());
      System.out.println("排序后的数据集: " + dataset);
  
      // 3. 截取区间 [1, 4) 的子视图并直接修改
      List<Integer> subView = dataset.subList(1, 4);
      System.out.println("子视图内容: " + subView);
      subView.set(0, 999); // 修改子视图
      System.out.println("母列表受子视图同步影响后的状态: " + dataset);
  
      // 4. 利用 ListIterator 进行反向遍历
      ListIterator<Integer> it = dataset.listIterator(dataset.size());
      System.out.print("反向迭代输出: ");
      while (it.hasPrevious()) {
        System.out.print(it.previous() + " ");
      }
      System.out.println();
    }
  }

注意事项

注意事项:

1. subList 视图的并发修改崩溃（CME 风险）：

   subList 生成的不是一个独立的新集合，而是母列表的一个内部视窗。在获取 subList 之后，如果直接对母列表执行了任何结构性变更（如 add 或 remove），会导致母列表的 modCount 发生改变。此时只要再次操作子视图，就会抛出 ConcurrentModificationException。

2. 基本数据类型自动装箱导致的 remove() 重载歧义：

   当线性表指定为 List<Integer> 时，调用 remove(1) 默认会匹配 remove(int index)（删除索引为 1 的元素）。如果业务意图是删除数值为 1 的元素，必须显式调用 remove(Integer.valueOf(1)) 来强行匹配 remove(Object o) 重载。

3. 不可变线性表的写操作限制：

   由 List.of() 或 List.copyOf() 创建的容器属于严格只读状态。对其执行任何 add()、remove() 或 set() 操作都会直接抛出 UnsupportedOperationException。

实战：待办任务管理器

本案例实现一个符合生产规范的简易待办任务管理器（TaskManager）。该系统使用 ArrayList 作为存储介质，演示了任务的添加、按优先级调整顺序、状态更新、删除以及遍历输出等高频 List 操作。

import java.util.ArrayList;
import java.util.List;

/**
 * 任务实体类
 */
class Task {
    private final int id;
    private final String description;
    private boolean isCompleted;

    public Task(int id, String description) {
        this.id = id;
        this.description = description;
        this.isCompleted = false;
    }

    public int getId() { return id; }
    public String getDescription() { return description; }
    public boolean isCompleted() { return isCompleted; }
    public void setCompleted(boolean completed) { isCompleted = completed; }

    @Override
    public String toString() {
        return "Task [ID=" + id + ", 描述=" + description + ", 状态=" + (isCompleted ? "已完成" : "未完成") + "]";
    }
}

/**
 * 任务管理核心类
 */
public class TaskManager {
    // 使用 List 统一管理系统内的所有任务
    private final List<Task> taskList = new ArrayList<>();

    /**
     * 追加普通任务到末尾
     */
    public void appendTask(Task task) {
        if (task == null) return;
        taskList.add(task);
    }

    /**
     * 将紧急任务插入到队列首位
     */
    public void insertUrgentTask(Task task) {
        if (task == null) return;
        taskList.add(0, task);
    }

    /**
     * 依据索引更新指定任务的状态
     */
    public void completeTask(int index) {
        if (index < 0 || index >= taskList.size()) {
            System.err.println("错误：索引越界，无法更新任务。");
            return;
        }
        Task task = taskList.get(index);
        task.setCompleted(true);
    }

    /**
     * 依据索引移除已失效的任务
     */
    public void removeTask(int index) {
        if (index < 0 || index >= taskList.size()) {
            System.err.println("错误：索引越界，无法删除任务。");
            return;
        }
        Task removed = taskList.remove(index);
        System.out.println("系统提示：成功移除任务 -> " + removed.getDescription());
    }

    /**
     * 打印当前所有任务状态
     */
    public void printAllTasks() {
        System.out.println("------ 当前任务看板 ------");
        for (int i = 0; i < taskList.size(); i++) {
            System.out.println("位置 [" + i + "] " + taskList.get(i));
        }
        System.out.println("------------------------");
    }

    public static void main(String[] args) {
        TaskManager manager = new TaskManager();

        // 1. 模拟录入常规任务
        manager.appendTask(new Task(101, "编写商业需求设计文档"));
        manager.appendTask(new Task(102, "执行系统集成回归测试"));

        // 2. 插入紧急任务到队首
        manager.insertUrgentTask(new Task(999, "修复生产环境 OOM 异常阻断问题"));

        // 打印初始看板
        manager.printAllTasks();

        // 3. 处理并完成队首的紧急任务
        manager.completeTask(0);

        // 4. 移除已经不再需要的常规任务（此时回归测试在索引 2）
        manager.removeTask(2);

        // 打印最终处理后的看板
        manager.printAllTasks();
    }
}

List-ArrayList~

java.util.ArrayList 是 Java 集合框架中基于动态数组实现的列表结构。它继承自 AbstractList 并实现了 List、RandomAccess、Cloneable 以及 Serializable 接口。其核心特征是通过连续的内存空间存储对象引用，支持以 $O(1)$ 的时间复杂度进行高效的随机元素访问。

底层数据结构

ArrayList 的底层其实非常朴素，它的核心成员变量就是一个普通的成员数组：

transient Object[] elementData; // 真正存储元素的数组
private int size;               // 实际存储的元素个数

因为它本质上是数组，所以它天然继承了数组的优缺点：支持通过索引快速随机访问，但在中间插入或删除元素时需要移动大量元素。

注意事项:

1. ArrayList 中存储的是对象的引用，而非对象本身，因此底层数组的类型为 Object[]。

2. 实现了 RandomAccess 接口标志着该类支持快速随机访问，在遍历时使用传统的 for 循环（基于索引）效率高于使用 Iterator 迭代器。

   import java.util.ArrayList;
   import java.util.List;
   import java.util.RandomAccess;
   
   public class ArrayListStructureDemo {
    public static void main(String[] args) {
        // 初始化一个 ArrayList
        List<String> list = new ArrayList<>();
        list.add("Element1");
        list.add("Element2");
   
        // 验证 RandomAccess 接口特性
        if (list instanceof RandomAccess) {
            System.out.println("ArrayList 实现了 RandomAccess 接口，推荐使用索引遍历。");
            for (int i = 0; i < list.size(); i++) {
                System.out.println("索引 " + i + " 处的元素: " + list.get(i));
            }
        }
    }
   }

动态扩容

作为动态数组，ArrayList 不需要我们在初始化时就定死长度，它会在空间不足时自动长大。

1. 懒加载（Lazy Initialization）：

   当你通过 new ArrayList<>() 创建一个无参的列表时，为了节省内存，Java 并没有立刻为你分配空间，而是将 elementData 指向了一个空数组。只有在第一次调用 add() 方法添加元素时，才会将数组扩容到默认的初始容量：10。

2. 倍扩容算法：

   当数组满了（即 size == elementData.length），再次添加元素就会触发扩容。扩容的底层逻辑如下：

   1. 计算新容量： 新容量 = 旧容量 + (旧容量 >> 1)。也就是原容量的 1.5 倍（右移 1 位相当于除以 2）。
   2. 内存申请与拷贝： 创建一个容量为 1.5 倍的新数组，然后调用 Arrays.copyOf() 方法，将老数组中的元素全部复制到新数组中。
   3. 引用切换： 将 elementData 指向新数组，老数组等待垃圾回收（GC）。

注意事项：

1. 扩容涉及新数组分配与全量数据拷贝，属于高耗时操作。在明确已知数据规模时，应显式指定初始容量，以规避频繁扩容带来的性能损耗。
2. 扩容的最大容量上限通常为 Integer.MAX_VALUE - 8，以防止部分 JVM 在数组头信息分配时溢出。

import java.util.ArrayList;

public class ArrayListResizeDemo {
 public static void main(String[] args) {
     // 显式指定初始容量，避免频繁扩容
     ArrayList<Integer> optimizedList = new ArrayList<>(100);

     // 批量写入数据
     for (int i = 0; i < 50; i++) {
         optimizedList.add(i);
     }
     System.out.println("当前元素数量: " + optimizedList.size());
 }
}

随机访问

ArrayList 实现的 RandomAccess 接口是一个标记接口（Marker Interface），用来表明该容器支持高效的随机访问（可以在 $O(1)$ 时间复杂度下通过索引直接获取元素）。由于其底层的连续内存特性，它在遍历时展现出了极高的 CPU 缓存亲和度。

import java.util.ArrayList;
import java.util.List;
import java.util.RandomAccess;

public class ArrayListArchitectureDemo {
  public static void main(String[] args) {
    ArrayList<String> arrayList = new ArrayList<>();

    // 验证接口契约：ArrayList 实现了 RandomAccess
    if (arrayList instanceof RandomAccess) {
      System.out.println("架构验证：ArrayList 具备高效的随机访问（RandomAccess）能力。");
    }

    // 验证多态架构：向上转型为 List 接口引用
    List<String> listRef = arrayList;
    listRef.add("Node_Data");
    System.out.println("多态引用输出: " + listRef);
  }
}

线程不安全

ArrayList 不是线程安全的。如果多个线程同时操作同一个 ArrayList 且没有同步措施，可能会导致数据覆盖、索引越界（ArrayIndexOutOfBoundsException）或者 size 计数错误。

Fail-Fast 机制

API：ArrayList

构造与空间优化

构造与空间优化:

• ArrayList ArrayList()：()，构造一个初始容量为 10 的空列表（采用延迟初始化策略，在首次执行 add 操作时才真正分配内存）。

• ArrayList ArrayList()：(int initialCapacity)，构造一个具有指定初始容量的空列表。适合预知数据规模时使用，避免多次扩容。

• ArrayList ArrayList()：(Collection<? extends E> c)，构造一个包含指定集合元素的列表，元素顺序由集合的迭代器决定。

• void trimToSize()：()，将底层数组容量调整为当前实际元素大小（size），用以释放空闲的内存空间。

• void ensureCapacity()：(int minCapacity)，手动扩大底层数组容量，确保其至少能容纳指定数量的元素，用以减少连续插入时的系统开销。

  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  public class ArrayListConstructorDemo {
   public static void main(String[] args) {
       // 1. 指定容量构造
       ArrayList<String> listWithCapacity = new ArrayList<>(50);
  
       // 2. 集合转换构造
       List<String> sourceCollection = Arrays.asList("Java", "Go", "Python");
       ArrayList<String> listFromCollection = new ArrayList<>(sourceCollection);
  
       // 3. 空间优化
       listFromCollection.add("C++");
       listFromCollection.trimToSize(); // 将底层数组容量缩减至 4
  
       System.out.println("初始化完成的集合: " + listFromCollection);
   }
  }

元素增删改查

元素增删改查:

• boolean add()：(E e)，将指定的元素追加到列表的尾部。成功返回 true。时间复杂度为均摊 $O(1)$。

• void add()：(int index, E element)，在列表的指定索引位置插入指定元素，原索引及后续元素依次向后移动。时间复杂度为 $O(n)$。

• E remove()：(int index)，移除列表中指定索引位置的元素，将后续元素向前平移，并返回被移除的元素。时间复杂度为 $O(n)$。

• boolean remove()：(Object o)，从列表中移除首次出现的指定元素（基于 equals 判断）。若存在并移除返回 true。

• E set()：(int index, E element)，用指定元素替换列表中指定索引处的元素，并返回被替换的旧元素。

• E get()：(int index)，返回列表中指定索引位置的元素。时间复杂度为 $O(1)$。

  import java.util.ArrayList;
  
  public class ArrayListCrudDemo {
   public static void main(String[] args) {
       ArrayList<String> devices = new ArrayList<>();
  
       // 尾部追加
       devices.add("Phone");
       devices.add("Computer");
  
       // 指定位置插入
       devices.add(1, "Tablet"); // 当前：[Phone, Tablet, Computer]
  
       // 快速读取
       String firstElement = devices.get(0);
  
       // 修改元素
       String oldVal = devices.set(2, "Server"); // Computer 被替换为 Server
  
       // 移除元素
       devices.remove(1); // 移除 Tablet
       devices.remove("Phone"); // 按对象移除 Phone
  
       System.out.println("剩余设备: " + devices + " | 曾被替换的旧元素: " + oldVal);
   }
  }

状态检索与遍历

状态检索与遍历:

• int size()：()，返回列表中的实际元素个数。

• boolean isEmpty()：()，检查列表是否为空（即 size == 0）。

• boolean contains()：(Object o)，判定列表是否包含指定元素。底层依赖 indexOf(o) 的返回值是否大于等于 0。

• int indexOf()：(Object o)，返回指定元素在列表中首次出现的索引；若不存在则返回 -1。

• void clear()：()，清空列表中的所有元素。底层将所有数组槽位赋值为 null 以便于垃圾回收，并重置 size 为 0。

  import java.util.ArrayList;
  
  public class ArrayListSearchDemo {
   public static void main(String[] args) {
       ArrayList<String> tags = new ArrayList<>();
       tags.add("Docker");
       tags.add("K8s");
       tags.add("Docker");
  
       // 状态检查
       boolean emptyCheck = tags.isEmpty();
       int totalSize = tags.size();
  
       // 检索元素位置
       boolean hasK8s = tags.contains("K8s");
       int firstDockerIndex = tags.indexOf("Docker");
  
       // 清空列表
       tags.clear();
  
       System.out.println("清空前容量: " + totalSize + " | 是否含K8s: " + hasK8s + " | 首次出现Docker索引: " + firstDockerIndex);
       System.out.println("清空后是否为空: " + tags.isEmpty());
   }
  }

实战：学生信息库管理系统

本案例基于 ArrayList 实现对学生数据的增删改查。它规避了直接并发修改的技术缺陷，使用索引优化遍历，提供完整的业务控制流程。

import java.util.ArrayList;
import java.util.Objects;

/**
 * 学生实体类
 */
class Student {
    private final String id;
    private String name;
    private double score;

    public Student(String id, String name, double score) {
        this.id = id;
        this.name = name;
        this.score = score;
    }

    public String getId() { return id; }
    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public double getScore() { return score; }
    public void setScore(double score) { this.score = score; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{学号='" + id + "', 姓名='" + name + "', 成绩=" + score + "}";
    }
}

/**
 * 学生管理库系统
 */
class StudentRepository {
    // 预设初始容量为 20，减少扩容成本
    private final ArrayList<Student> storage = new ArrayList<>(20);

    /**
     * 添加学生信息
     */
    public boolean addStudent(Student student) {
        if (student == null || storage.contains(student)) {
            return false;
        }
        return storage.add(student);
    }

    /**
     * 根据学号删除学生信息
     */
    public boolean removeStudent(String id) {
        int index = findIndexById(id);
        if (index != -1) {
            storage.remove(index); // 基于索引移除，性能优于直接 remove(Object)
            return true;
        }
        return false;
    }

    /**
     * 修改学生分数
     */
    public boolean updateScore(String id, double newScore) {
        int index = findIndexById(id);
        if (index != -1) {
            Student student = storage.get(index); // O(1) 随机访问
            student.setScore(newScore);
            return true;
        }
        return false;
    }

    /**
     * 打印全体学生数据
     */
    public void displayAll() {
        System.out.println("--- 全体学生花名册 (总人数: " + storage.size() + ") ---");
        // 遵循 RandomAccess 标准，采用基于索引的 for 循环以提升效率
        for (int i = 0; i < storage.size(); i++) {
            System.out.println(storage.get(i));
        }
    }

    /**
     * 内部私有工具方法：按学号检索对应索引位置
     */
    private int findIndexById(String id) {
        for (int i = 0; i < storage.size(); i++) {
            if (storage.get(i).getId().equals(id)) {
                return i;
            }
        }
        return -1;
    }
}

/**
 * 运行主入口
 */
public class StudentManagementSystem {
    public static void main(String[] args) {
        StudentRepository repository = new StudentRepository();

        // 1. 录入数据
        repository.addStudent(new Student("1001", "张三", 89.5));
        repository.addStudent(new Student("1002", "李四", 94.0));
        repository.addStudent(new Student("1003", "王五", 76.0));

        // 2. 打印当前名册
        repository.displayAll();

        // 3. 修改指定学生分数
        System.out.println("\n更新学号为 1001 的学生成绩...");
        repository.updateScore("1001", 95.5);

        // 4. 移除指定学号学生
        System.out.println("移除学号为 1003 的学生信息...");
        repository.removeStudent("1003");

        // 5. 打印最终变更名册
        repository.displayAll();
    }
}

List-LinkedList~

双向链表实现

双向链表实现:

java.util.LinkedList 底层基于双向链表（Doubly Linked List）结构实现。与基于动态数组的 ArrayList 不同，LinkedList 的内存空间是不连续的。链表中的每个独立节点通过内部类 Node 实例来表示。

每个 Node 节点包含三个核心要素：

private static class Node<E> {
    E item;       // 存储当前节点的实际数据元素。
    Node<E> next; // 指向下一个节点的指针（引用）
    Node<E> prev; // 指向上一节点的指针（引用）
}

LinkedList 类内部维护了两个指针：first（指向链表的头节点）和 last（指向链表的尾节点）。这种结构使得在链表的头部和尾部进行插入、删除操作的时间复杂度为 $O(1)$。

import java.util.LinkedList;

public class LinkedListStructureDemo {
 public static void main(String[] args) {
     // 初始化一个标准的 LinkedList 实例
     LinkedList<String> list = new LinkedList<>();

     // 元素的双向链接构建
     list.add("Node A"); // 此时 first 和 last 都指向 Node A
     list.add("Node B"); // Node A.next -> Node B, Node B.prev -> Node A
     list.add("Node C"); // Node B.next -> Node C, Node C.prev -> Node B

     // 打印输出以确认链表元素
     System.out.println("链表当前数据: " + list);
 }
}

时间复杂度

因为数据结构完全不同，LinkedList 的性能特征与 ArrayList 恰好相反：

• 随机访问 get(int index) / set(int index, E element)：$O(n)$

  链表没有索引下标！你想找第 500 个元素，必须从头（或从尾）开始沿着指针一个一个数过去。

  源码小优化： LinkedList 在根据索引查找时做了一个二分判断。如果要找的索引小于总长度的一半（index < (size >> 1)），就从前往后找；否则从后往前找。但这依然改变不了它 $O(n)$ 的本质。

• 头部/尾部插入与删除 addFirst() / removeLast()：$O(1)$

  只需要修改一下 first 或 last 指针的指向即可，不需要移动任何内存数据，速度极快。

• 中间插入与删除 add(int index, E element)：均摊 $O(n)$

  虽然插入/删除动作本身（改指针）是 $O(1)$ 的，但是为了把指针走到指定的 index 位置，必须先经历一段 $O(n)$ 的寻路过程。

使用场景

在现代 Java 开发中，大多数情况下，你应该默认选择 ArrayList。现代 CPU 的缓存行（Cache Line）对连续的内存（如数组）极其友好，其遍历性能远超链表。

只有在以下场景，才建议使用 LinkedList：

1. 你的业务频繁在集合的头部进行插入、删除操作。

2. 你需要一个标准的队列（Queue）或双端队列（Deque）来做任务调度（不过如果追求更高性能，现代开发更推荐使用 ArrayDeque）。

API：LinkedList

构造方法

构造方法:

• LinkedList LinkedList()：()，构造一个空列表，不预分配任何空间。

• LinkedList LinkedList()：(Collection<? extends E> c)，构造一个包含指定集合元素的列表，元素的排列顺序由该集合的迭代器返回。

  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.LinkedList;
  
  public class ConstructorDemo {
   public static void main(String[] args) {
       // 1. 无参构造
       LinkedList<Integer> emptyList = new LinkedList<>();
  
       // 2. 带有初始化集合的构造
       Collection<Integer> sourceCollection = new ArrayList<>();
       sourceCollection.add(100);
       sourceCollection.add(200);
  
       LinkedList<Integer> collectionList = new LinkedList<>(sourceCollection);
       System.out.println("基于集合构造的链表内容: " + collectionList);
   }
  }

列表核心操作

列表核心操作:

• boolean add()：(E e)，将指定元素追加到列表的末尾。

• void add()：(int index, E element)，在列表的指定位置（索引）插入指定的元素。

• E get()：(int index)，返回列表中指定位置的元素。内部使用二分查找法判定从头或从尾遍历。

• E remove()：(int index)，移除并返回列表中指定位置的元素，需要修正前后节点的指针指向。

• int size()：()，返回列表中包含的元素个数。

  import java.util.LinkedList;
  
  public class ListOperationsDemo {
   public static void main(String[] args) {
       LinkedList<String> list = new LinkedList<>();
  
       // 追加元素
       list.add("Element 1");
       list.add("Element 3");
  
       // 指定位置插入
       list.add(1, "Element 2"); // 插入到索引 1 的位置
  
       // 检索元素
       String element = list.get(1);
       System.out.println("索引 1 处的元素: " + element);
  
       // 移除元素
       String removed = list.remove(2);
       System.out.println("被移除的元素: " + removed);
       System.out.println("最终链表大小: " + list.size());
   }
  }

双端队列与栈操作

双端队列与栈操作（Deque & Queue 接口实现）:

• void addFirst()：(E e)，将指定元素插入此列表的开头。

• void addLast()：(E e)，将指定元素追加到此列表的末尾。

• E peekFirst()：()，获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。

• E pollFirst()：()，获取并移除此列表的第一个元素；如果此列表为空，则返回 null。

• void push()：(E e)，将元素推入此列表所表示的栈。等同于 addFirst(e)。

• E pop()：()，从此列表所表示的栈中弹出一个元素。等同于 removeFirst()。

  import java.util.LinkedList;
  
  public class DequeOperationsDemo {
   public static void main(String[] args) {
       LinkedList<String> deque = new LinkedList<>();
  
       // 双端队列头尾添加
       deque.addFirst("Head");
       deque.addLast("Tail");
  
       // 安全获取头元素
       System.out.println("队头元素 (peek): " + deque.peekFirst());
  
       // 安全弹出头元素
       System.out.println("出队元素 (poll): " + deque.pollFirst());
  
       // 模拟栈操作
       LinkedList<String> stack = new LinkedList<>();
       stack.push("Bottom");
       stack.push("Top");
       System.out.println("弹栈元素: " + stack.pop());
   }
  }

注意事项

1. 性能陷阱与随机访问高开销：

   LinkedList 不支持高效的随机访问（Random Access）。当调用 get(int index) 检索元素时，即使内部优化为了根据 index 与 size / 2 的关系决定从头还是从尾遍历，其时间复杂度依然是 $O(n)$。因此，严禁使用传统的 for (int i = 0; i < list.size(); i++) 循环去遍历 LinkedList，这会导致 $O(n^2)$ 的时间复杂度。应当统一使用 Iterator 或增强型 for 循环（foreach）。

2. 内存开销较多：

   相比于 ArrayList 连续的底层数组，LinkedList 的每一个节点都需要额外创建 Node 对象，并包含 prev 和 next 两个引用。在存储相同数量的同类型元素时，LinkedList 带来的内存碎片及对象头、引用指针的内存开销明显偏大。

3. 线程不安全行为：

   LinkedList 不是线程安全的。如果有多个线程同时并发访问并修改同一个链表，必须显式对其进行外部同步，或者通过 Collections.synchronizedList 方法将其包装。

   import java.util.Collections;
   import java.util.LinkedList;
   import java.util.List;
   import java.util.ConcurrentModificationException;
   import java.util.Iterator;
   
   public class CaveatsDemo {
     public static void main(String[] args) {
       // 1. 线程安全包装示例
       List<String> syncList = Collections.synchronizedList(new LinkedList<>());
       syncList.add("Safe Element");
   
       // 2. 迭代器并发修改异常 (Fail-Fast) 演示
       LinkedList<String> list = new LinkedList<>();
       list.add("A");
       list.add("B");
   
       try {
         Iterator<String> iterator = list.iterator();
         while (iterator.hasNext()) {
           String val = iterator.next();
           if ("A".equals(val)) {
             list.add("C"); // 触发 Fail-Fast 机制
           }
         }
       } catch (ConcurrentModificationException e) {
         System.out.println("捕获到预期的异常: ConcurrentModificationException (由于在迭代中直接修改了集合)");
       }
     }
   }

实战：双端队列应用

基础双端队列应用：撤销/重做（Undo/Redo）管理器:

在许多文本编辑器或图形工具中，用户的操作需要支持撤销（Undo）和重做（Redo）。利用 LinkedList 作为双端队列和栈的特性，可以高效地实现该功能。

import java.util.LinkedList;

/**
 * 文本编辑器的撤销与重做动作管理器
 */
public class ActionManager {
    // 存储已提交的历史动作（栈结构）
    private final LinkedList<String> undoStack = new LinkedList<>();
    // 存储已撤销的动作，用于重做（栈结构）
    private final LinkedList<String> redoStack = new LinkedList<>();

    /**
     * 用户执行新操作
     */
    public void executeAction(String action) {
        undoStack.push(action);
        // 每当有新操作产生，清空重做队列
        redoStack.clear();
        System.out.println("执行操作: [" + action + "]");
    }

    /**
     * 撤销操作
     */
    public void undo() {
        if (undoStack.isEmpty()) {
            System.out.println("没有可撤销的操作。");
            return;
        }
        String action = undoStack.pop();
        redoStack.push(action);
        System.out.println("撤销操作: [" + action + "]");
    }

    /**
     * 重做操作
     */
    public void redo() {
        if (redoStack.isEmpty()) {
            System.out.println("没有可重做的操作。");
            return;
        }
        String action = redoStack.pop();
        undoStack.push(action);
        System.out.println("重做操作: [" + action + "]");
    }

    /**
     * 打印当前状态
     */
    public void printStatus() {
        System.out.println("当前历史栈 (Undo Stack): " + undoStack);
        System.out.println("当前重做栈 (Redo Stack): " + redoStack);
        System.out.println("----------------------------------------");
    }

    public static void main(String[] args) {
        ActionManager manager = new ActionManager();

        // 模拟用户输入和操作流程
        manager.executeAction("键入 'Hello'");
        manager.executeAction("键入 ' World'");
        manager.executeAction("加粗字体");
        manager.printStatus();

        // 撤销两步
        manager.undo();
        manager.undo();
        manager.printStatus();

        // 重做一步
        manager.redo();
        manager.printStatus();

        // 发生新操作
        manager.executeAction("插入图片");
        manager.printStatus(); // 此时 Redo 栈应已被清空
    }
}

List-Vector~

体系架构

体系架构:

java.util.Vector 是 Java 集合框架中历史最悠久的线性表实现类之一，自 JDK 1.0 便已存在。在 JDK 1.2 集合框架重构时，Vector 被统一适配，直接继承自 java.util.AbstractList，并实现了 java.util.List、java.util.RandomAccess、java.lang.Cloneable 以及 java.io.Serializable 接口。

由于其全线方法均集成了内置同步机制，Vector 是一个线程安全（Thread-Safe）的同步动态数组。

import java.util.List;
import java.util.RandomAccess;
import java.util.Vector;

public class VectorArchitectureDemo {
  public static void main(String[] args) {
    Vector<String> vector = new Vector<>();

    // 验证体系契约：Vector 属于 List 体系且支持高效随机访问
    if (vector instanceof List && vector instanceof RandomAccess) {
      System.out.println("架构验证：Vector 实现了 List 接口与 RandomAccess 标记接口。");
    }

    // 多态视窗切换
    List<String> listRef = vector;
    listRef.add("Legacy_Node");
    System.out.println("数据输出: " + listRef);
  }
}

核心原理

核心原理:

Vector 的底层核心技术座是一块连续分配的内部对象数组 Object[] elementData。其与现代 ArrayList 的核心差异主要体现在互斥同步与扩容步长算法上：

1. 方法级粗粒度锁：

   Vector 内部几乎所有涉及读取、写入和结构变更的公共方法，都显式加上了 synchronized 关键字（修饰符）。这意味着多线程并发访问同一个 Vector 实例时，所有操作都必须串行化竞争该实例的对象锁，从而确保了内部数据的一致性，但这也带来了极高的线程互斥开销。

2. $2$ 倍或指定步长扩容机制：

   当触发写入且当前 size 即将超越底层数组容量时，系统激活 ensureCapacityHelper(int minCapacity) 内部方法。

   其扩容公式为：

   $$\text{newCapacity} = \text{oldCapacity} + ((\text{capacityIncrement} > 0) ? \text{capacityIncrement} : \text{oldCapacity})$$

   如果在构造时指定了正整数的 capacityIncrement（容量增量），则每次扩容时底层数组大小会固定加上该步长值；若未指定（即该值为 0），底层数组容量默认直接翻倍（$2$ 倍扩容）。

import java.util.Vector;
import java.lang.reflect.Field;

public class VectorResizingMechanismDemo {
  public static void main(String[] args) throws Exception {
    // 1. 构建一个初始容量为 5，扩容步进值为 3 的 Vector
    Vector<Integer> customVector = new Vector<>(5, 3);
    System.out.println("--- 步进值扩容测试 ---");
    fillAndPrintCapacity(customVector, 5); // 填满 5 个元素

    customVector.add(6); // 触发扩容：预期 5 + 3 = 8
    printInternalCapacity(customVector);

    // 2. 构建一个默认的 Vector (无参构造，初始容量为 10，步进值为 0)
    Vector<Integer> defaultVector = new Vector<>();
    System.out.println("\n--- 默认翻倍扩容测试 ---");
    fillAndPrintCapacity(defaultVector, 10); // 填满 10 个元素

    defaultVector.add(11); // 触发扩容：预期 10 + 10 = 20
    printInternalCapacity(defaultVector);
  }

  private static void fillAndPrintCapacity(Vector<Integer> v, int count) throws Exception {
    for (int i = 1; i <= count; i++) v.add(i);
    printInternalCapacity(v);
  }

  private static void printInternalCapacity(Vector<?> v) throws Exception {
    Field field = Vector.class.getDeclaredField("elementData");
    field.setAccessible(true);
    Object[] elementData = (Object[]) field.get(v);
    System.out.println("Size: " + v.size() + " | 物理底层数组容量 (Capacity): " + elementData.length);
  }
}

API：Vector

构造与容量控制

构造与容量控制:

• Vector Vector()：()，构造一个空向量，其内部数据数组的初始大小为 10，标准容量增量为 0。

• Vector Vector()：(int initialCapacity, int capacityIncrement)，构造一个具有指定初始容量和容量增量的空向量。

• void setSize()：(int newSize)，设置此向量的大小。若新大小大于当前大小，则追加新元素并赋予 null 引用；若小于当前大小，则丢弃索引边界外的所有过剩元素。

  import java.util.Vector;
  
  public class VectorCapacityApiDemo {
    public static void main(String[] args) {
      // 配置初始空间为 2，后续扩容步长为 4
      Vector<String> manager = new Vector<>(2, 4);
  
      manager.add("Task1");
      manager.add("Task2");
  
      // 强行改变线性表尺寸
      manager.setSize(4);
      System.out.println("强制变更 size 后的向量内容: " + manager);
      System.out.println("此时索引 2 处的值: " + manager.get(2)); // 预期为 null
    }
  }

遗留专属操作

遗留专属操作（JDK 1.2 适配前原生 API）:

• void addElement()：(E obj)，将指定的组件添加到此向量的末尾，同步确保其大小加 1。功能完全等价于 add(E)。

• E elementAt()：(int index)，返回指定索引处的组件。功能完全等价于 get(int)。

• Enumeration<E> elements()：()，返回此向量的组件的枚举（Enumeration）。属于传统的早期迭代器视图模型。

  import java.util.Enumeration;
  import java.util.Vector;
  
  public class VectorLegacyApiDemo {
    public static void main(String[] args) {
      Vector<String> legacyContainer = new Vector<>();
  
      // 1. 使用 JDK 1.0 遗留旧方法注入与读取数据
      legacyContainer.addElement("Legacy_A");
      legacyContainer.addElement("Legacy_B");
  
      String element = legacyContainer.elementAt(0);
      System.out.println("elementAt 检索结果: " + element);
  
      // 2. 导出旧版 Enumeration 迭代视图
      Enumeration<String> enumeration = legacyContainer.elements();
      System.out.print("Enumeration 遍历结果: ");
      while (enumeration.hasMoreElements()) {
        System.out.print("[" + enumeration.nextElement() + "] ");
      }
      System.out.println();
    }
  }

注意事项

注意事项:

1. 粗粒度同步导致的严重性能耗损：

   由于 Vector 所有的核心读写操作均由 synchronized 全局锁控制，在单线程环境下，这会导致无谓的锁获取与释放开销；在多线程高并发环境下，则会引起严重的锁竞争与线程阻塞瓶颈。因此，单线程下首选 ArrayList，并发场景下首选 java.util.concurrent.CopyOnWriteArrayList。

2. 复合操作（Compound Actions）的非原子性隐患：

   虽然 Vector 的单个方法（如 size()、get()）都是线程安全的，但将它们组合成复合业务逻辑时（例如：“若不存在则添加”：if(!vector.contains(e)) vector.add(e); 或传统的条件循环遍历），复合操作本身并不是原子的。在高并发错乱交织执行时，依然必须在外部手动对整个 Vector 实例加锁才能确保绝对安全。

3. 双倍扩容带来的堆内存激增压力：

   在不显式指定步进值（capacityIncrement）的情况下，Vector 默认采用翻倍扩容。当容器内的数据基数达到数百万级别时，一次扩容就会瞬间申请成倍的连续大数组空间，这极易引发内存碎片化及 java.lang.OutOfMemoryError。

实战：高并发全链路应用日志异步收集器

以下案例模拟了一个企业级多线程“高并发全链路应用日志异步收集器”。该系统需要在多线程并发上报、日志高吞吐写入的场景下工作，同时为了防止突发流量导致的内存无限翻倍爆破，案例中显式指定了 Vector 的扩容步进值（capacityIncrement）进行内存限额，并在外部对复合操作（日志清空提取）进行了原子化封装。

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * 全流式日志审计报文实体
 */
class AuditLog {
  private final String threadName;
  private final String logMessage;
  private final long timestamp;

  public AuditLog(String threadName, String logMessage) {
    this.threadName = threadName;
    this.logMessage = logMessage;
    this.timestamp = System.currentTimeMillis();
  }

  @Override
  public String toString() {
    return "[" + timestamp + "][" + threadName + "] -> " + logMessage;
  }
}

/**
 * 异步日志收集缓冲区（核心业务组件）
 */
public class ConcurrentLogCollector {

  // 构建一个显式限制扩容跨度的 Vector 实例：初始分配 50 空间，每次溢出固定递增 20，规避翻倍导致的 OOM
  private final Vector<AuditLog> logBuffer = new Vector<>(50, 20);

  /**
     * 并发写入日志：利用 Vector 自身的方法级线程安全特性
     */
  public void pushLog(String message) {
    AuditLog payload = new AuditLog(Thread.currentThread().getName(), message);
    logBuffer.addElement(payload); // 线程安全追加
  }

  /**
     * 复合操作：安全排干并提取当前缓冲区内的全部日志。
     * 必须在外部进行整体锁定，才能确保“读取”后“清空”的原子性。
     */
  public List<AuditLog> flushAndDrain() {
    // 对内部集合实例加锁，固化整个复合动作边界
    synchronized (logBuffer) {
      if (logBuffer.isEmpty()) {
        return new ArrayList<>();
      }

      // 1. 批量拷贝当前镜像
      List<AuditLog> snapshot = new ArrayList<>(logBuffer);
      // 2. 原地结构化清空
      logBuffer.clear();

      return snapshot; // 返回已被物理断开的安全快照
    }
  }

  public static void main(String[] args) throws InterruptedException {
    ConcurrentLogCollector collector = new ConcurrentLogCollector();
    // 模拟 4 个工作线程并发上报日志数据
    ExecutorService workerPool = Executors.newFixedThreadPool(4);

    System.out.println("=== 异步高并发审计收集引擎启动 ===");

    for (int i = 0; i < 12; i++) {
      final int index = i;
      workerPool.submit(() -> {
        collector.pushLog("业务流水数据报文节点-" + index);
      });
    }

    // 等待并发任务结束
    workerPool.shutdown();
    workerPool.awaitTermination(3, TimeUnit.SECONDS);

    // 执行安全的复合提取操作
    System.out.println("\n--- 核心消费链启动：执行原子级排干清洗 ---");
    List<AuditLog> processedLogs = collector.flushAndDrain();

    System.out.println("成功从同步向量容器中排干提取的日志数: " + processedLogs.size());
    processedLogs.forEach(System.out.println);
  }
}

Set~

核心原理

核心原理:

java.util.Set 是 Java 集合框架中的核心接口之一，它继承自 java.util.Collection 接口。Set 接口的核心行为特征是：不允许包含重复元素。在其主流实现中，最多只允许包含一个 null 元素。Set 接口没有引入新的抽象方法，它完全继承了 Collection 的方法签名，但对这些方法确立了更严格的契约约束（例如 add 方法在尝试添加重复元素时必须返回 false）。

核心特性

1. 不允许重复元素：这是 Set 最显著的特点。如果尝试将已存在的元素加入 Set，add() 方法会返回 false，且集合不会发生改变。

2. 最多允许一个 null 元素：由于不能重复，Set 最多只能容纳一个 null（注意：部分实现类如 TreeSet 甚至不允许 null）。

3. 不保证顺序：标准的 Set 接口不保证元素的迭代顺序（具体取决于实现类）。

4. 没有索引：与 List 不同，Set 没有提供类似 get(int index) 的方法，你不能通过下标来获取元素，通常需要通过迭代器（Iterator）或增强型 for 循环来遍历。

核心实现类

Java 提供了几种不同的 Set 实现，应对不同的应用场景：

1. HashSet（最常用）：

   • 底层结构：基于 HashMap 实现（元素的行为其实就是 HashMap 的 Key）。
   • 特点：查找、添加和删除操作性能极高，时间复杂度为 $O(1)$。
   • 顺序：完全无序。元素的排列顺序甚至可能随着元素的增加而发生改变。
   • 应用场景：当你需要一个高性能的去重容器，且不在乎元素的顺序时。

2. LinkedHashSet：

   • 底层结构：继承自 HashSet，内部引入了双向链表来记录元素的插入顺序。
   • 特点：性能略低于 HashSet（因为需要维护链表），但迭代开销较小。
   • 顺序：保证插入顺序。遍历时，元素流出的顺序就是它们被添加进去的顺序。
   • 应用场景：需要去重，同时又需要保持用户输入/插入的先后顺序时。

3. TreeSet：

   • 底层结构：基于 TreeMap（红黑树，一种自平衡二叉查找树）实现。
   • 特点：操作的时间复杂度为 $O(\log n)$。不允许放入 null 值。
   • 顺序：保证元素处于排序状态（升序）。元素必须实现 Comparable 接口，或者在创建 TreeSet 时提供自定义的 Comparator。
   • 应用场景：需要去重，并且要求集合中的元素随时处于排序状态。

三大实现类对比:

特性	HashSet	LinkedHashSet	TreeSet
底层实现	HashMap (哈希表)	LinkedHashMap (哈希表+双向链表)	TreeMap (红黑树)
元素顺序	无序	插入顺序	自然顺序/自定义排序
查找/插入时间复杂度	$O(1)$	$O(1)$	$O(\log n)$
内存开销	小	较大 (每个节点需额外存前后指针)	中等 (树节点有左右子节点指针)
使用场景	仅去重，不在乎顺序，追求极致性能	既要去重，又要求维持输入顺序	既要去重，又要求元素按大小自动排序

API：Set

Set 中的方法都是继承自 Collection，它自身没有新增的方法。

基础操作

基础操作功能组:

• boolean add()：(E e)，向集合中添加指定元素。若集合中尚未包含该元素，则添加成功并返回 true；若集合中已存在该元素，则不改变集合并返回 false。

• boolean remove()：(Object o)，从集合中移除指定元素。若集合中存在该元素且成功移除，则返回 true。

• boolean contains()：(Object o)，判断集合中是否包含指定元素，如果包含则返回 true。

• int size()：()，返回集合中的元素数量（集合的基数）。

• boolean isEmpty()：()，判断当前集合是否为空，若不包含任何元素则返回 true。

  import java.util.HashSet;
  import java.util.Set;
  
  public class SetBaseExample {
    public static void main(String[] args) {
      Set<String> set = new HashSet<>();
  
      // 1. 添加元素并验证去重返回值
      System.out.println("添加 'Java': " + set.add("Java")); // 返回 true
      System.out.println("重复添加 'Java': " + set.add("Java")); // 返回 false
      set.add("Go");
  
      // 2. 检查集合状态
      System.out.println("是否包含 'Java': " + set.contains("Java"));
      System.out.println("集合当前元素数量: " + set.size());
      System.out.println("集合是否为空: " + set.isEmpty());
  
      // 3. 移除元素
      System.out.println("移除 'Go': " + set.remove("Go")); // 返回 true
      System.out.println("当前集合内容: " + set);
    }
  }

集合运算

集合运算功能组:

• boolean addAll()：(Collection<? extends E> c)，求并集。将指定集合中的所有元素添加到当前集合中（排除重复）。

• boolean retainAll()：(Collection<?> c)，求交集。仅保留当前集合中同时包含在指定集合中的元素。

• boolean removeAll()：(Collection<?> c)，求差集。从当前集合中移除包含在指定集合中的所有元素。

• boolean containsAll()：(Collection<?> c)，判断当前集合是否包含指定集合中的所有元素（即指定集合是否为当前集合的子集）。

  import java.util.Arrays;
  import java.util.HashSet;
  import java.util.Set;
  
  public class SetOperationExample {
    public static void main(String[] args) {
      Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
      Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5));
  
      // 1. 并集运算
      Set<Integer> union = new HashSet<>(set1);
      union.addAll(set2);
      System.out.println("并集结果: " + union); // [1, 2, 3, 4, 5]
  
      // 2. 交集运算
      Set<Integer> intersection = new HashSet<>(set1);
      intersection.retainAll(set2);
      System.out.println("交集结果: " + intersection); // [3]
  
      // 3. 差集运算
      Set<Integer> difference = new HashSet<>(set1);
      difference.removeAll(set2);
      System.out.println("差集结果 (set1 - set2): " + difference); // [1, 2]
  
      // 4. 子集判断
      boolean isSubset = set1.containsAll(Arrays.asList(1, 2));
      System.out.println("set1 是否包含子集 [1, 2]: " + isSubset); // true
    }
  }

Set-HashSet~

java.util.HashSet 是 Java 集合框架中最常用的 Set 接口实现类。其核心特性是不保证元素的迭代顺序，且允许存放 null 元素（最多一个）。

核心特性

在深入底层之前，我们先用一句话总结 HashSet 的脾气：

• 不允许重复：如果尝试添加重复元素，旧元素不会被覆盖，add() 方法直接返回 false。

• 允许 null 值：但因为去重特性，最多只能存一个 null。

• 完全无序：

  • 这里的无序不等于随机性，而是根据添加元素的哈希值计算出其在数组中的存储位置，该位置不是依次排序的，表现为无序性。
  • 它不保证元素的任何顺序。既不是插入顺序，也不是字母/数字大小顺序。甚至随着集合内元素的增加，原本的顺序还可能会发生改变（扩容导致的重新哈希）。

• 线程不安全：多线程并发修改 HashSet 时，需要手动同步（如使用 Collections.synchronizedSet）或使用并发容器（如 ConcurrentHashMap 的 KeySet 视图）。

底层是 HashMap

很多人以为 HashSet 内部有一套复杂的哈希算法，但实际上，HashSet 只是对 HashMap 的一层完美包装。

如果你翻开 JDK 的 HashSet 源码，你会发现它的内部竟然套着一个 HashMap：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
  // 1. 内部其实就是一个 HashMap
  private transient HashMap<E,Object> map;

  // 2. 作为一个 Dummy Value（哑值/傀儡值），用来充当 HashMap 的 Value
  private static final Object PRESENT = new Object();

  // 3. 构造方法直接 new 了一个 HashMap
  public HashSet() {
    map = new HashMap<>();
  }

  // 4. add 方法本质上是把元素当做 Key 存入 map
  public boolean add(E e) {
    return map.put(e, PRESENT) == null;
  }
}

它是如何工作的：

当你看懂了源码，HashSet 的面纱就揭开了：

• 当你往 HashSet 存入一个元素 e 时，它在底层其实是调用了 map.put(e, PRESENT)。
• 你的元素成了 HashMap 的 Key。
• 而 HashMap 的 Value，则统一使用一个共享的、毫无意义的空对象 PRESENT。

由于 HashMap 的 Key 具备天然的唯一性，HashSet 借此直接复用了 HashMap 的去重机制，从而保证了自身的高效与数据唯一性。

扩容与性能调优

因为底层是 HashMap，HashSet 的大部分基本操作（如 add, remove, contains）在理想情况下的时间复杂度都是 $O(1)$。这意味着无论集合里有 10 个元素还是 100 万个元素，查找速度几乎是一样快的。

为了维持这种高效，HashSet 的性能主要受两个参数影响：

1. 初始容量 (Initial Capacity)：哈希表中桶（Bucket）的数量。创建时如果不指定，默认是 16。

2. 加载因子 (Load Factor)：衡量哈希表满强度的指标。默认是 0.75。

   扩容临界点 = 初始容量 $\times$ 加载因子。

   例如：$16 \times 0.75 = 12$。当 HashSet 中的元素超过 12 个时，底层就会触发自动扩容（容量翻倍变成 32），并对所有元素进行一轮 rehash（重新计算位置）。

哈希碰撞与去重机制@

这是面试和实际开发中最容易踩坑的地方。当调用 add(E e) 时，HashSet 判定重复的逻辑如下：

1. 计算 HashCode：首先调用该对象的 hashCode() 方法，计算出它的哈希值。

2. 桶位比对：根据哈希值找到对应的桶。

   • 如果桶里没有其他元素，直接放进去。
   • 如果桶里已有其他元素（发生哈希冲突），则进行第二步比对。

3. equals() 终审：拿着新元素和该桶位里的老元素逐个进行 == 或 equals() 比较。

   • 如果 equals() 返回 true，对不起，认定为重复元素，拒绝加入。
   • 如果 equals() 返回 false，说明只是恰好哈希冲突了，它们是不同的对象。在 Java 8 中，会以链表或红黑树的形式挂在同一个桶位下面。

黄金法则：重写 equals 必须重写 hashCode:

如果你创建了一个自定义类（比如 User），并希望根据 id 去重，你必须同时重写这两个方法。

• 如果你只重写了 equals：会默认调用 Object 中的 hashCode() 方法，该方法不同的对象返回的哈希值不同，即便对象的属性值都一样。两个 id 相同的对象，因为 hashCode 不同，会被分到不同的桶里，HashSet 根本没机会调用 equals 去对比它们，从而导致去重失败。

API：HashSet

构造方法

• HashSet HashSet()：()，构造一个空的 HashSet 实例，底层 HashMap 的默认初始容量为 16，负载因子为 0.75。

• HashSet HashSet()：(int initialCapacity)，构造一个空的 HashSet 实例，指定其底层的初始容量，负载因子使用默认的 0.75。

• HashSet HashSet()：(int initialCapacity, float loadFactor)，构造一个空的 HashSet 实例，同时指定其底层的初始容量与负载因子。

• HashSet HashSet()：(Collection<? extends E> c)，构造一个包含指定集合中所有元素的 HashSet 实例。

  import java.util.ArrayList;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  
  public class HashSetConstructorDemo {
   public static void main(String[] args) {
       // 1. 默认无参构造
       Set<String> set1 = new HashSet<>();
  
       // 2. 指定初始容量构造（预知要存入 10 个元素，设为 16 避免扩容）
       Set<String> set2 = new HashSet<>(16);
  
       // 3. 指定初始容量与负载因子（极高吞吐或极端内存限制场景）
       Set<String> set3 = new HashSet<>(32, 0.6f);
  
       // 4. 基于已有集合进行复制构造与去重
       List<String> rawList = new ArrayList<>();
       rawList.add("Apple");
       rawList.add("Banana");
       rawList.add("Apple"); // 重复元素
  
       Set<String> set4 = new HashSet<>(rawList);
       System.out.println("Set4 元素内容: " + set4); // 输出: [Apple, Banana]
   }
  }

基本操作

• boolean add()：(E e)，向集合中添加指定元素。若元素已存在则放弃添加并返回 false。

• boolean remove()：(Object o)，从集合中移除指定的元素。若元素存在并成功移除，返回 true。

• boolean contains()：(Object o)，判断集合中是否包含指定的元素，若包含则返回 true。

• int size()：()，返回当前集合中存储的非重复元素总总数量。

• boolean isEmpty()：()，检查当前集合是否不包含任何元素。

• void clear()：()，清空当前集合中的所有元素，将其重置为空状态。

  import java.util.HashSet;
  import java.util.Set;
  
  public class HashSetMethodsDemo {
   public static void main(String[] args) {
       Set<Integer> numberSet = new HashSet<>();
  
       // 1. 测试添加与去重返回值
       System.out.println("添加 100: " + numberSet.add(100)); // true
       System.out.println("重复添加 100: " + numberSet.add(100)); // false
       numberSet.add(200);
  
       // 2. 检查集合状态
       System.out.println("当前元素数量 (size): " + numberSet.size()); // 2
       System.out.println("是否包含 200: " + numberSet.contains(200)); // true
  
       // 3. 移除元素
       System.out.println("移除 100: " + numberSet.remove(100)); // true
       System.out.println("移除后的集合: " + numberSet); // [200]
  
       // 4. 清空集合
       numberSet.clear();
       System.out.println("清空后是否为空: " + numberSet.isEmpty()); // true
   }
  }

注意事项

注意事项:

1. 契约一致性约束： 任何作为 HashSet 元素的类，必须同时重写 hashCode() 和 equals() 方法，且必须保证两者的计算业务逻辑完全一致。如果两个对象通过 equals() 判定为相等，它们的 hashCode() 返回值也必须绝对相等。

2. 元素对象属性的不可变性：

   当一个对象被放入 HashSet 后，严禁修改任何参与 hashCode() 计算的属性字段。一旦这些属性发生改变，该对象的哈希值也会随之改变，这将导致它在底层哈希桶中变成“幽灵对象”——你无法通过 contains() 找到它，也无法通过 remove() 卸载它，从而造成严重的内存泄漏。

   

3. 非线程安全与 Fail-Fast 机制：

   HashSet 不是线程安全的。若多个线程并发访问并修改同一个 HashSet，必须通过外部加锁，或者使用 Collections.synchronizedSet(new HashSet<>()) 进行包装。其迭代器具备 Fail-Fast（快速失败） 机制，在迭代过程中，如果检测到集合结构被直接修改（非通过迭代器自身的 remove 方法），将直接抛出 ConcurrentModificationException。

实战：用户行为日志分析

本案例模拟一个电商系统的用户行为日志分析组件。该组件需要从大量的原始访问请求中，高效提取出在特定时间段内访问过系统的独立访客主键（UUID），并过滤非法或重复的请求数据。

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * 访客设备唯一标识领域类
 */
class VisitorDevice {
    private final String deviceUuid;
    private final String osType;

    public VisitorDevice(String deviceUuid, String osType) {
        this.deviceUuid = deviceUuid;
        this.osType = osType;
    }

    public String getDeviceUuid() {
        return deviceUuid;
    }

    // 重写 equals 和 hashCode 确保基于设备唯一 UUID 进行去重
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        VisitorDevice that = (VisitorDevice) o;
        return Objects.equals(deviceUuid, that.deviceUuid);
    }

    @Override
    public int hashCode() {
        return Objects.hash(deviceUuid);
    }

    @Override
    public String toString() {
        return "Device{" + "uuid='" + deviceUuid + '\'' + ", os='" + osType + '\'' + '}';
    }
}

/**
 * 独立访客日志去重分析器
 */
public class VisitorLogAnalyzer {

    // 模拟非法的恶意刷量设备黑名单
    private static final Set<String> BLACKLIST_UUIDS = new HashSet<>();

    static {
        BLACKLIST_UUIDS.add("UUID_ERR_9999");
        BLACKLIST_UUIDS.add("UUID_SPAM_0000");
    }

    public static void main(String[] args) {
        // 初始化独立访客去重池
        Set<VisitorDevice> uniqueVisitors = new HashSet<>();

        // 模拟高并发流入的原始设备访问日志
        VisitorDevice log1 = new VisitorDevice("UUID_A8801", "iOS");
        VisitorDevice log2 = new VisitorDevice("UUID_B3202", "Android");
        VisitorDevice log3 = new VisitorDevice("UUID_A8801", "iOS"); // 重复请求（同设备正常多点击）
        VisitorDevice log4 = new VisitorDevice("UUID_SPAM_0000", "Windows"); // 恶意刷量请求

        System.out.println("--- 开始执行日志流清洗与统计 ---");
        processLog(uniqueVisitors, log1);
        processLog(uniqueVisitors, log2);
        processLog(uniqueVisitors, log3);
        processLog(uniqueVisitors, log4);

        System.out.println("\n--- 清洗完毕 ---");
        System.out.println("当前统计周期的独立访客数 (UV): " + uniqueVisitors.size());
        System.out.println("有效访客设备明细: " + uniqueVisitors);
    }

    /**
     * 处理单条日志并并入去重池
     */
    private static void processLog(Set<VisitorDevice> pool, VisitorDevice device) {
        // 1. 安全过滤检查
        if (BLACKLIST_UUIDS.contains(device.getDeviceUuid())) {
            System.err.println("安全拦截 -> 发现黑名单设备，拒绝计入: " + device.getDeviceUuid());
            return;
        }

        // 2. 利用 HashSet 契约进行去重沉淀
        boolean isNewVisitor = pool.add(device);
        if (isNewVisitor) {
            System.out.println("日志录入 -> 成功计入新独立访客: " + device);
        } else {
            System.out.println("日志忽略 -> 检测到重复设备访问，已自动去重: " + device.getDeviceUuid());
        }
    }
}

Set-HashSet-LinkedHashSet~

java.util.LinkedHashSet 是 HashSet 的直接子类。它在继承了 HashSet 去重核心契约的基础上，引入了可预知的迭代顺序。具体而言，LinkedHashSet 的迭代顺序严格遵循元素的插入顺序（Insertion-Order）。如果在集合中重新插入一个已经存在的元素，其原有位置和顺序不会受到任何影响。

核心特性

1. 保证插入顺序：这是它与 HashSet 的最大区别。当你遍历 LinkedHashSet 时，元素的流出顺序与你当初 add() 进去的顺序完全一致。

2. 性能略低于 HashSet，但依然高效：

   • 基本操作时间复杂度：借助于哈希表，其 add()、contains()、remove() 等核心方法的常数时间复杂度仍保持在 $O(1)$ 级别，仅由于需要维护双向链表指针，其整体常数开销略大于 HashSet。
   • 遍历性能优于 HashSet：HashSet 的遍历时间取决于哈希表的总容量与元素密度的乘积（需要扫描整个桶数组）；而 LinkedHashSet 的遍历时间仅与当前集合内元素的实际数量 $n$ 成正比（$O(n)$），因此在元素稀疏且需要频繁遍历的场景下，LinkedHashSet 的迭代效率显著高于 HashSet。

3. 允许一个 null 值：与 HashSet 一样，最多只能容纳一个 null。

4. 不允许重复：继承自 Set 的底线，任何重复元素都无法被加入。

底层数据结构

LinkedHashSet 的底层并不直接创建新的数据结构，而是完全依赖于 java.util.LinkedHashMap。

在 HashSet 的源码中，存在一个专门为 LinkedHashSet 提供的包私有（package-private）构造方法：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

当实例化 LinkedHashSet 时，会通过 super 关键字隐式调用上述构造方法。因此，LinkedHashSet 内置的 map 成员变量的实际运行时类型是 LinkedHashMap。

LinkedHashMap 中的每个节点（LinkedHashMap.Entry）除了继承 HashMap.Node 的 hash、key、value 和 next 指针外，还额外维护了两个指针：

• before：指向前一个插入的节点。
• after：指向后一个插入的节点。

在底层的 LinkedHashMap 中，它不仅有一个哈希表（数组+链表/红黑树） 结构，还额外维护了一条由这组双向指针将原本分散在各个哈希桶中的节点串联成的双向链表（Doubly Linked List）。这条双向链表将所有存入集合的节点按照插入的先后顺序串联了起来。

• 当你在做 contains(e) 查找时：它利用哈希表快速定位，速度是 $O(1)$。
• 当你在做迭代遍历（如 for-each）时：它不再去扫描无序的哈希表，而是直接沿着这条双向链表从头走到尾。因此，遍历 LinkedHashSet 的效率甚至比标准 HashSet 还要高，因为它的消耗只和集合内“实际元素的数量”有关，而与“哈希表的总容量”无关。

API：LinkedHashSet

构造方法

• LinkedHashSet LinkedHashSet()：()，构造一个空的、具有默认初始容量 (16) 和负载因子 (0.75) 的可预知迭代顺序的 LinkedHashSet 实例。

• LinkedHashSet LinkedHashSet()：(int initialCapacity)，构造一个空的、具有指定初始容量和默认负载因子 (0.75) 的 LinkedHashSet 实例。

• LinkedHashSet LinkedHashSet()：(int initialCapacity, float loadFactor)，构造一个空的、具有指定初始容量和指定负载因子的 LinkedHashSet 实例。

• LinkedHashSet LinkedHashSet()：(Collection<? extends E> c)，构造一个包含指定集合中所有元素的 LinkedHashSet 实例。元素的排列顺序为它们在原集合中迭代器返回的顺序。

  import java.util.Arrays;
  import java.util.LinkedHashSet;
  import java.util.List;
  import java.util.Set;
  
  public class LinkedHashSetConstructorDemo {
    public static void main(String[] args) {
      // 1. 默认无参构造
      Set<String> linkedSet1 = new LinkedHashSet<>();
  
      // 2. 指定初始容量构造（预知存储 8 个元素，防扩容损耗）
      Set<String> linkedSet2 = new LinkedHashSet<>(16);
  
      // 3. 基于已有集合构造并维持原始顺序
      List<String> rawList = Arrays.asList("Z", "A", "F", "A", "Z");
      Set<String> linkedSet3 = new LinkedHashSet<>(rawList);
  
      // 验证去重且顺序保持一致 (输出: [Z, A, F])
      System.out.println("保持插入顺序的去重集合: " + linkedSet3);
    }
  }

基本操作

• boolean add()：(E e)，向集合尾部追加指定元素。若集合已包含该元素，则不执行插入且保持原有的位置顺序不变。

• Iterator<E> iterator()：()，返回在此集合元素上进行迭代的迭代器。迭代器将严格按照元素被首次存入的先后顺序进行异步遍历。

  import java.util.Iterator;
  import java.util.LinkedHashSet;
  import java.util.Set;
  
  public class LinkedHashSetMethodsDemo {
    public static void main(String[] args) {
      Set<String> tasks = new LinkedHashSet<>();
  
      // 1. 顺次添加元素
      tasks.add("Task-1");
      tasks.add("Task-2");
      tasks.add("Task-3");
  
      // 2. 尝试重复添加已存在的元素 "Task-2"
      boolean isAdded = tasks.add("Task-2");
      System.out.println("重复追加 Task-2 是否成功: " + isAdded); // false
  
      // 3. 按插入顺序遍历输出
      System.out.print("当前任务执行队列: ");
      Iterator<String> iterator = tasks.iterator();
      while (iterator.hasNext()) {
        System.out.print(iterator.next() + " -> ");
      }
      // 输出结果严格为: Task-1 -> Task-2 -> Task-3 ->
    }
  }

注意事项

1. 内存占用开销（Memory Overhead）

   由于 LinkedHashSet 底层使用了双向链表来包裹数据节点，每一个节点都需要额外承担两个引用（before 和 after）的内存开销。在内存资源极度紧张或需要存储数亿级别海量数据的场景下，应优先考虑 HashSet 以节约内存。

2. 重复插入的位置静止契约

   LinkedHashSet 维护的是元素首次插入时的顺序。如果一个元素已经在集合中存在，再次调用 add() 方法虽然会返回 false，但并不会将该元素移动到链表的末尾。如果业务场景需要实现“最近最少使用（LRU）”这类随访问/重入而改变顺序的特性，应当直接使用 LinkedHashMap 并开启其 access-order 配置。

3. 线程安全性与并发修改

   LinkedHashSet 同样是非线程安全的。如果在多线程并发读写的场景下使用，必须采用外部同步策略：

   Set<Type> syncLinkedSet = Collections.synchronizedSet(new LinkedHashSet<>());

并且由于其迭代器采用了 Fail-Fast 机制，在用 Iterator 或 for-each 遍历集合时，任何在迭代器范围之外对集合结构的修改（如直接调用 set.remove()）都会立即抛出 ConcurrentModificationException。

实战：用户浏览记录管理

本案例模拟一个电商系统的“用户浏览足迹清洗模块”。当用户在短时间内频繁跨页面浏览商品时，系统会产生大量的日志。为了精准进行用户意图画像分析，我们需要过滤掉其中高频、重复的商品 ID，但必须绝对保留用户首次访问各商品的先后物理顺序。

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
   * 用户浏览行为日志实体
   */
class FootprintLog {
  private final Long productId;
  private final String category;

  public FootprintLog(Long productId, String category) {
    this.productId = productId;
    this.category = category;
  }

  public Long getProductId() {
    return productId;
  }

  // 重写 equals 和 hashCode，使去重业务逻辑聚焦于商品主键 productId
  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    FootprintLog log = (FootprintLog) o;
    return Objects.equals(productId, log.productId);
  }

  @Override
  public int hashCode() {
    return Objects.hash(productId);
  }

  @Override
  public String toString() {
    return "商品[" + productId + "(" + category + ")]";
  }
}

/**
   * 浏览足迹物理流分析组件
   */
public class FootprintAnalyzer {
  public static void main(String[] args) {
    // 1. 模拟上游实时流入的用户原始浏览日志（其中存在高频往复点击的噪声数据）
    List<FootprintLog> rawLogs = new ArrayList<>();
    rawLogs.add(new FootprintLog(101L, "手机数码"));
    rawLogs.add(new FootprintLog(102L, "图书音像"));
    rawLogs.add(new FootprintLog(101L, "手机数码")); // 噪声：短时间内回看
    rawLogs.add(new FootprintLog(103L, "户外运动"));
    rawLogs.add(new FootprintLog(102L, "图书音像")); // 噪声：重复点击
    rawLogs.add(new FootprintLog(104L, "服装配饰"));

    System.out.println("=== 原始流入的浏览日志流 ===");
    rawLogs.forEach(log -> System.out.println("用户浏览 -> " + log));

    // 2. 利用 LinkedHashSet 在保持物理先后顺序的前提下进行高效去重
    Set<FootprintLog> cleanSequence = new LinkedHashSet<>(rawLogs);

    System.out.println("\n=== 经过清洗后的用户纯净浏览时间线 ===");
    // 输出将完美契合用户触达商品的原始客观顺序：101 -> 102 -> 103 -> 104
    int step = 1;
    for (FootprintLog uniqueLog : cleanSequence) {
      System.out.println("阶段 " + (step++) + ": " + uniqueLog);
    }

    // 3. 模拟业务消费：将清洗后的数据输出给推荐引擎
    System.out.println("\n[系统提示] 成功生成该用户的有序足迹画像，核心意图序列长度为: " + cleanSequence.size());
  }
}

Set-TreeSet~

java.util.TreeSet 是 Set 接口的另一个核心实现类，它实现了 java.util.NavigableSet 接口（该接口扩展了 java.util.SortedSet）。与 HashSet 和 LinkedHashSet 不同，TreeSet 的核心特征是保证集合内的元素处于有序状态。

核心特性

1. 元素自动排序：存入 TreeSet 的元素会根据某种“排序规则”自动进行升序排列。你遍历它时，拿到的数据永远是有序的。

2. 绝对不允许 null 值：往 TreeSet 里添加 null 会直接抛出 NullPointerException（因为没办法拿 null 和其他对象比大小）。

3. 性能为 $O(\log n)$：由于需要维护排序结构，它的插入、删除、查找操作的时间复杂度是 $O(\log n)$，虽然比 HashSet 的 $O(1)$ 慢，但也非常高效。

4. 判定重复的规则很特殊：它不依赖 equals() 和 hashCode()，而是依赖 compareTo() 或 compare() 方法。如果两个元素比较结果为 0，TreeSet 就认为它们是重复的。

5. 元素独一无二：继承自 Set 接口，不允许重复元素。

底层数据结构

TreeSet 的底层完全基于 java.util.TreeMap 实例来实现。在源码中，系统同样将 TreeSet 的元素作为 TreeMap 的 Key 进行存储，而 Value 则统一指向同一个虚拟的 PRESENT 对象。

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
  this.m = m;
}

节点寻址与平衡控制

TreeMap 的底层数据结构是红黑树（Red-Black Tree）——一种自平衡的二叉查找树：

当执行 add(e) 写入操作时，树会从根节点（Root）开始，逐层进行二分比较：

• 若新 e 小于当前节点 e，则走向左子树。
• 若新 e 大于当前节点 e，则走向右子树。
• 若比较结果返回 0，则判定键重复，直接使用新 e 覆盖旧 e，并返回旧 e。

每次完成插入或删除节点后，为了防止二叉树退化为线性链表，TreeMap 内部会通过红黑树的五大性质（如根节点为黑色、红节点的子节点必须为黑色等）进行校验，并通过左旋、右旋和节点变色操作，确保树的高度始终控制在 $\log n$ 级别。

为什么选择红黑树:

• 严格的物理顺序： 红黑树的左子节点小于根节点，右子节点大于根节点。通过中序遍历红黑树，可以得到一个绝对升序的序列。
• 稳定的性能保证： 无论是插入、删除还是查找操作，TreeMap 的时间复杂度都能稳定在 $O(\log n)$。虽然它没有 HashMap 在理想状态下的 $O(1)$ 那么快，但在最坏情况下，它绝不会像未优化的单链表那样退化到 $O(n)$。

import java.util.TreeMap;
import java.util.Map;

public class TreeMapCoreDemo {
  public static void main(String[] args) {
      // 基于自然排序（String 默认按字典序升序）
      Map<String, Integer> treeMap = new TreeMap<>();

      // 错序写入
      treeMap.put("Zebra", 1);
      treeMap.put("Apple", 2);
      treeMap.put("Monkey", 3);

      // 迭代输出，结果会自动转化为字典升序：Apple -> Monkey -> Zebra
      for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
          System.out.println(entry.getKey() + " : " + entry.getValue());
      }
  }
}

排序和去重机制@

TreeSet 的排序与去重机制完全脱离了对象的 hashCode() 和 equals() 方法，而是严格依赖于元素的比较逻辑。

排序机制

TreeSet 支持两种排序方式：

• 自然排序（Natural Ordering）：元素对象所属的类必须实现 java.lang.Comparable 接口，并重写 compareTo(E o) 方法。
• 定制排序（Custom Ordering）：在构造 TreeSet 时，传入一个实现了 java.util.Comparator<E> 接口的比较器对象，重写 compare(E o1, E o2) 方法。

去重机制

这是 TreeSet 最显著的特性约束：当且仅当两个元素通过比较方法（compareTo 或 compare）返回结果为 0 时，TreeSet 才会认为这两个元素是重复的，进而拒绝后续元素的写入。

这一机制打破了 Collection 接口基于 equals 判等的常规契约。如果一个类的 compare 方法与 equals 方法的判定结果不一致，TreeSet 的行为将会违反 Set 的通用契约。

compareTo vs equals

这是初学者和面试中最容易翻车的地方！

HashSet 靠 equals() 认人，TreeSet 靠 compareTo() 认人。

如果往 TreeSet 存入自定义对象，一旦你的 compareTo() 逻辑写得不严谨，就会引发灾难。

惨案现场代码:

class Student implements Comparable<Student> {
  String name;
  int age;

  public Student(String name, int age) { this.name = name; this.age = age; }

  @Override
  public int compareTo(Student o) {
    // 逻辑：只根据年龄比大小
    return this.age - o.age;
  }
}

翻车后果：

如果你往 TreeSet 里添加 new Student("张三", 18) 和 new Student("李四", 18)。

因为他们的年龄都是 18，compareTo 会返回 0。TreeSet 会判定“李四”是重复元素，直接拒绝让他加入！ “李四”就这样无缘无故地丢了，尽管两者的名字完全不同。

避坑准则：

确保你的 compareTo() 或 compare() 方法的返回值，与 equals() 的逻辑保持高度一致。只有当两个对象真正意义上完全相等时，才让它返回 0。

@Override
public int compareTo(Student s) {
  int ageCompare = Integer.compare(this.age, s.age);
  if (ageCompare != 0) {
    return ageCompare;
  }
  return this.name.compareTo(s.name);
}

@Override
public boolean equals(Object o) {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  Student s = (Student) o;
  return Integer.compare(s.age, age) == 0 && Objects.equals(name, s.name);
}

API：TreeSet

构造方法

• TreeSet TreeSet()：()，构造一个空的 TreeSet，它根据元素的自然顺序（实现 Comparable 接口）进行排序。

• TreeSet TreeSet()：(Comparator<? super E> comparator)，构造一个空的 TreeSet，它根据指定的比较器进行定制排序。

• TreeSet TreeSet()：(Collection<? extends E> c)，构造一个包含指定集合中所有元素的 TreeSet，根据元素的自然顺序进行排序。

  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.Set;
  import java.util.TreeSet;
  
  public class TreeSetConstructorDemo {
    public static void main(String[] args) {
      // 1. 自然排序构造（String 默认实现了 Comparable 接口）
      Set<String> naturalSet = new TreeSet<>();
      naturalSet.add("Zebra");
      naturalSet.add("Apple");
      System.out.println("自然排序结果: " + naturalSet); // [Apple, Zebra]
  
      // 2. 定制排序构造（通过匿名内部类或 Lambda 传入降序比较器）
      Set<Integer> customSet = new TreeSet<>((o1, o2) -> Integer.compare(o2, o1));
      customSet.addAll(Arrays.asList(5, 1, 9, 3));
      System.out.println("定制降序结果: " + customSet); // [9, 5, 3, 1]
    }
  }

导航与区间检索

• E first()：()，返回当前集合中当前的第一个（最小的）元素。

• E last()：()，返回当前集合中当前的最后一个（最大的）元素。

• E floor()：(E e)，返回当前集合中小于或等于给定元素的最高元素（$\le e$）；若不存在则返回 null。

• E ceiling()：(E e)，返回当前集合中大于或等于给定元素的最低元素（$\ge e$）；若不存在则返回 null。

• E lower()：(E e)，返回当前集合中严格小于给定元素的最高元素；若不存在则返回 null。

• E higher()：(E e)，返回当前集合中严格大于给定元素的最低元素；若不存在则返回 null。

• NavigableSet<E> subSet()：(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)，返回当前集合指定区间的视图。通过布尔值控制是否包含边界。

  import java.util.NavigableSet;
  import java.util.TreeSet;
  
  public class TreeSetNavigationDemo {
    public static void main(String[] args) {
      NavigableSet<Integer> scores = new TreeSet<>();
      scores.add(60);
      scores.add(75);
      scores.add(85);
      scores.add(90);
      scores.add(100);
  
      // 1. 边界检索
      System.out.println("最低分: " + scores.first()); // 60
      System.out.println("最高分: " + scores.last());  // 100
  
      // 2. 邻近值检索
      System.out.println("严格小于 85 的最高分 (lower): " + scores.lower(85));   // 75
      System.out.println("严格大于 90 的最低分 (higher): " + scores.higher(90)); // 100
      System.out.println("小于或等于 85 的最高分 (floor): " + scores.floor(85)); // 85
      System.out.println("大于或等于 88 的最低分 (ceiling): " + scores.ceiling(88)); // 90
  
      // 3. 区间截取（获取 75 分到 90 分之间的子集视图，包含 75，不包含 90）
      NavigableSet<Integer> scope = scores.subSet(75, true, 90, false);
      System.out.println("区间视图结果: " + scope); // [75, 85]
    }
  }

注意事项

1. 拒绝 null 元素（Null Disallowance）

   由于 TreeSet 在写入元素时必须调用比较方法（compareTo 或 compare），而 null 对象无法调用方法或参与比较。因此，向 TreeSet 中尝试添加 null 元素会直接抛出 NullPointerException（即便使用的是定制比较器，除非该比较器内部显式编写了允许 null 传递的容错逻辑，但这通常不推荐）。

2. 比较器与 Equals 的协调约束

   如果通过 compare/compareTo 返回 0，而通过 equals 返回 false，将其存入 TreeSet 虽不会导致报错，但会导致 Set 无法根据官方定义的 equals 进行排重。这在与其它标准的 Collection 或者是依赖 equals 的第三方工具协同工作时，会引发隐蔽的业务逻辑 Bug。

3. 非线程安全与性能开销

   TreeSet 的每一次插入和删除都会引发红黑树的左旋、右旋或变色等自平衡调整。相较于 HashSet 的 $O(1)$ 常数级哈希碰撞，TreeSet 的 $O(\log n)$ 包含更多的指针断开与重连操作，性能开销稍高。它同样不是线程安全的，并发场景下应使用：

   SortedSet<Type> syncTreeSet = Collections.synchronizedSortedSet(new TreeSet<>());

   或并发包中的 java.util.concurrent.ConcurrentSkipListSet。

技术选型

• 选 HashSet：如果你只是单纯想去重，不需要管顺序，追求最高效的性能。
• 选 LinkedHashSet：如果你需要去重，同时希望保留元素原汁原味的插入先后顺序。
• 选 TreeSet：
  • 场景 A：需要集合内的元素随时处于某种排序状态（如游戏排行榜、动态更新的股票价格）。
  • 场景 B：需要进行范围查找或者寻找最接近的邻居元素（比如查找“在 100 到 200 之间的所有数据”，或者“大于 50 的最小数字”）。

实战：股票实时价格监控

本案例模拟一个证券交易系统的“股票实时价格监控调谐组件”。系统需要实时接收各股票的报价，不仅要求自动对价格从低到高进行排序，以便快速撮合交易，还需要提供基于特定价位区间的检索功能，用于触发投资者的价格预警通知。

import java.util.Objects;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * 股票行情快照类
 */
class StockTick implements Comparable<StockTick> {
  private final String symbol;
  private final double price;

  public StockTick(String symbol, double price) {
    this.symbol = symbol;
    this.price = price;
  }

  public String getSymbol() { return symbol; }
  public double getPrice() { return price; }

  /**
     * 实现 Comparable 接口契约
     * 业务规则：优先按价格升序排序；若价格绝对相等，则按股票代码字母序排序。
     */
  @Override
  public int compareTo(StockTick o) {
    int priceCompare = Double.compare(this.price, o.price);
    if (priceCompare != 0) {
      return priceCompare;
    }
    return this.symbol.compareTo(o.symbol);
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    StockTick stockTick = (StockTick) o;
    return Double.compare(stockTick.price, price) == 0 && Objects.equals(symbol, stockTick.symbol);
  }

  @Override
  public int hashCode() {
    return Objects.hash(symbol, price);
  }

  @Override
  public String toString() {
    return "Stock[" + symbol + " : $" + price + "]";
  }
}

/**
 * 股票价格监控与撮合分析引擎
 */
public class StockPriceEngine {
  public static void main(String[] args) {
    // 创建 TreeSet 容器，底层红黑树开始工作
    TreeSet<StockTick> tickerTree = new TreeSet<>();

    // 1. 模拟行情数据流入
    tickerTree.add(new StockTick("AAPL", 175.50));
    tickerTree.add(new StockTick("TSLA", 180.20));
    tickerTree.add(new StockTick("MSFT", 415.00));
    tickerTree.add(new StockTick("NVDA", 180.20)); // 与 TSLA 价格相同，但代码不同，不应被去重
    tickerTree.add(new StockTick("AAPL", 175.50)); // 绝对重复数据，应被去重

    System.out.println("=== 当前市场按价格升序排列的完整看板 ===");
    tickerTree.forEach(System.out.println);

    // 2. 核心撮合与极值查询
    System.out.println("\n=== 价格极值检索 ===");
    System.out.println("当前市场报价最低的股票: " + tickerTree.first());
    System.out.println("当前市场报价最高的股票: " + tickerTree.last());

    // 3. 触发区间价格预警通知
    // 业务需求：筛选出市场中价格在 $170.00 到 $200.00 之间的所有股票进行集中风险监控
    StockTick lowerBound = new StockTick("", 170.00);
    StockTick upperBound = new StockTick("", 200.00);

    SortedSet<StockTick> dangerZone = tickerTree.subSet(lowerBound, upperBound);

    System.out.println("\n=== 触发 [$170.00 - $200.00] 区间监控预警的股票 ===");
    for (StockTick tick : dangerZone) {
      System.out.println("⚠️ 预警提示 -> 股票: " + tick.getSymbol() + " 当前价: $" + tick.getPrice() + " 处于波动敏感区");
    }
  }
}

Queue~

概述与体系结构

概述与体系结构:

java.util.Queue 是 Java 集合框架（Java Collections Framework）的核心接口之一，用于模拟队列这种数据结构。队列通常遵循先进先出（FIFO, First-In-First-Out）的原则，即元素的插入操作在队尾（tail）进行，移除操作在队头（head）进行。但在特定子类实现中，这一规则可能发生变化（例如基于优先级的 PriorityQueue，或者双端队列 Deque）。

核心原理与方法体系

核心原理与方法体系:

Queue 接口定义了两套核心操作方法：一套在操作失败时抛出异常，另一套在操作失败时返回特殊值（null 或 false）。这种设计为并发或有界队列提供了极大的灵活性。

操作类型	抛出异常方法	返回特殊值方法	核心行为描述
插入（Insert）	add(e)	offer(e)	将元素插入队尾。若队列满，前者抛异常，后者返回 false。
移除（Remove）	remove()	poll()	移除并返回队头元素。若队列空，前者抛异常，后者返回 null。
检查（Examine）	element()	peek()	获取但不移除队头元素。若队列空，前者抛异常，后者返回 null。

API：Queue

插入操作组

插入操作组:

• boolean add()：(E e)，将指定元素插入当前队列的尾部。如果由于容量限制导致插入失败，则抛出 IllegalStateException。

• boolean offer()：(E e)，将指定元素插入当前队列的尾部。如果由于容量限制导致插入失败，则返回 false。在高并发或有界队列场景下推荐使用此方法。

  import java.util.LinkedList;
  import java.util.Queue;
  
  public class QueueInsertDemo {
   public static void main(String[] args) {
       Queue<String> queue = new LinkedList<>();
  
       // 使用 add 方法插入
       queue.add("Element A");
  
       // 使用 offer 方法插入
       boolean isSuccess = queue.offer("Element B");
  
       System.out.println("插入状态: " + isSuccess);
       System.out.println("当前队列: " + queue);
   }
  }

移除操作组

移除操作组:

• E remove()：()，检索并检索删除当前队列的队头元素。如果当前队列为空，则抛出 NoSuchElementException。

• E poll()：()，检索并删除当前队列的队头元素。如果当前队列为空，则返回 null。

  import java.util.LinkedList;
  import java.util.Queue;
  
  public class QueueRemoveDemo {
   public static void main(String[] args) {
       Queue<String> queue = new LinkedList<>();
       queue.offer("Element A");
       queue.offer("Element B");
  
       // 使用 poll 移除
       String firstRemoved = queue.poll();
       System.out.println("Poll 移除的元素: " + firstRemoved);
  
       // 使用 remove 移除
       String secondRemoved = queue.remove();
       System.out.println("Remove 移除的元素: " + secondRemoved);
  
       // 队列为空时测试
       String emptyPoll = queue.poll();
       System.out.println("空队列执行 Poll: " + emptyPoll); // 返回 null
   }
  }

检查操作组

检查操作组:

• E element()：()，检索但不删除当前队列的队头元素。如果当前队列为空，则抛出 NoSuchElementException。

• E peek()：()，检索但不删除当前队列的队头元素。如果当前队列为空，则返回 null。

  import java.util.LinkedList;
  import java.util.Queue;
  
  public class QueueExamineDemo {
   public static void main(String[] args) {
       Queue<String> queue = new LinkedList<>();
       queue.offer("Element A");
  
       // 使用 peek 检查
       String peekResult = queue.peek();
       System.out.println("Peek 检查结果: " + peekResult);
  
       // 使用 element 检查
       String elementResult = queue.element();
       System.out.println("Element 检查结果: " + elementResult);
   }
  }

注意事项

注意事项:

1. 严禁插入 null 元素：大部分 Queue 的实现（如 PriorityQueue、ArrayDeque）明确禁止插入 null。虽然 LinkedList 允许插入 null，但这属于不良实践，因为 poll() 和 peek() 在队列为空时会返回 null，如果队列中允许包含 null，将无法区分“队列为空”还是“队头元素本身就是 null”。

2. 线程安全性：java.util.Queue 接口下的通用实现类（LinkedList, PriorityQueue, ArrayDeque）全部是非线程安全的。如果在多线程并发环境下操作队列，必须使用 java.util.concurrent 包下的 BlockingQueue 系列组件（如 LinkedBlockingQueue、ArrayBlockingQueue）。

实战案例：订单排队处理系统

实战案例：订单排队处理系统:

以下案例模拟一个基础的高效订单排队系统。新生成的订单会进入队列，处理逻辑会依照 FIFO 原则依次将订单从队列中取出并处理。

import java.util.LinkedList;
import java.util.Queue;

public class OrderProcessingSystem {

    // 内部类：代表订单数据模型
    public static class Order {
        private final String orderId;
        private final double amount;

        public Order(String orderId, double amount) {
            this.orderId = orderId;
            this.amount = amount;
        }

        public String getOrderId() {
            return orderId;
        }

        public double getAmount() {
            return amount;
        }

        @Override
        public String toString() {
            return "Order{" + "orderId='" + orderId + '\'' + ", amount=" + amount + '}';
        }
    }

    public static void main(String[] args) {
        // 初始化业务订单队列（使用 LinkedList 实现类）
        Queue<Order> orderQueue = new LinkedList<>();

        // 1. 模拟系统接收到并发产生的一批业务订单（进入队尾）
        System.out.println("===== 阶段 1: 订单接收系统入队 =====");
        enqueueOrder(orderQueue, new Order("ORD_001", 128.50));
        enqueueOrder(orderQueue, new Order("ORD_002", 999.00));
        enqueueOrder(orderQueue, new Order("ORD_003", 45.00));

        // 2. 检查当前处于队头等待处理的第一笔订单（不移除）
        Order nextOrder = orderQueue.peek();
        if (nextOrder != null) {
            System.out.println("\n[系统检查] 下一个等待处理的队头订单: " + nextOrder.getOrderId());
        }

        // 3. 模拟后台核心业务逻辑对订单进行逐一消费（从队头出队）
        System.out.println("\n===== 阶段 2: 核心工作线程开始消费订单 =====");
        while (!orderQueue.isEmpty()) {
            Order currentOrder = orderQueue.poll(); // 安全出队
            if (currentOrder != null) {
                processOrder(currentOrder);
            }
        }

        System.out.println("\n[系统提示] 当前队列剩余订单数: " + orderQueue.size() + "，所有就绪订单处理完毕。");
    }

    private static void enqueueOrder(Queue<Order> queue, Order order) {
        boolean success = queue.offer(order);
        if (success) {
            System.out.println("[入队成功] " + order);
        } else {
            System.err.println("[入队失败] 订单队列已满，订单 ID: " + order.getOrderId());
        }
    }

    private static void processOrder(Order order) {
        System.out.println("[正在处理] 正在为 " + order.getOrderId() + " 扣减库存并扣款，金额: ￥" + order.getAmount());
    }
}

Queue-PriorityQueue~

概述与体系结构

概述与体系结构:

java.util.PriorityQueue 是 Java 集合框架中的一个基于优先级堆（Priority Heap）的无界队列。与标准的先进先出（FIFO）队列不同，PriorityQueue 中的元素根据其自然顺序（Natural Ordering）或者在创建队列时提供的 Comparator 进行排序。每次获取或移除操作流出的都是当前队列中优先级最高（权重最小或最大）的元素。

核心原理

核心原理:

PriorityQueue 底层基于平衡二叉最小堆（Balanced Binary Min-Heap）实现。物理上，它使用一个动态可变长的隐式数组（Object Array）来存储二叉树节点，从而避免了链表指针的额外内存开销。

堆的数组映射规则

堆的数组映射规则:

对于数组中任意索引为 $i$ 的元素：

• 其左子节点的索引为 $2i + 1$
• 其右子节点的索引为 $2i + 2$
• 其父节点的索引为 $\lfloor(i - 1) / 2\rfloor$

算法时间复杂度

算法时间复杂度:

• 插入元素 (offer)：$O(\log n)$，涉及向上的堆化调整（Sift Up）。

• 移除队头 (poll)：$O(\log n)$，涉及向下的堆化调整（Sift Down）。

• 检查队头 (peek)：$O(1)$，直接访问数组索引为 0 的元素。

• 检索或删除任意元素 (remove(Object))：$O(n)$，需要线性遍历数组定位目标元素。

  import java.util.PriorityQueue;
  import java.util.Queue;
  
  public class PriorityQueueOrderDemo {
   public static void main(String[] args) {
       Queue<Integer> pq = new PriorityQueue<>();
  
       // 乱序插入
       pq.offer(50);
       pq.offer(10);
       pq.offer(30);
  
       // 注意：直接打印 PriorityQueue 呈现的是底层数组的物理分布，并非排序结果
       System.out.println("数组物理分布: " + pq);
  
       // 只有通过循环 poll 才能展现优先级顺序
       System.out.print("逻辑出队顺序: ");
       while (!pq.isEmpty()) {
           System.out.print(pq.poll() + " "); // 输出 10 30 50
       }
   }
  }

API：PriorityQueue

构造方法组

构造方法组:

• PriorityQueue PriorityQueue()：()，创建一个默认初始容量（11）的 PriorityQueue，元素按照自然顺序（实现 Comparable 接口）进行升序排列。

• PriorityQueue PriorityQueue()：(int initialCapacity)，创建一个指定初始容量的 PriorityQueue，元素按照自然顺序排序。

• PriorityQueue PriorityQueue()：(Comparator<? super E> comparator)，创建一个默认初始容量（11）的 PriorityQueue，并使用定制的比较器确定元素优先级。

• PriorityQueue PriorityQueue()：(int initialCapacity, Comparator<? super E> comparator)，创建一个指定初始容量且使用定制比较器的 PriorityQueue。常用于高吞吐量下减少数组扩容频率的场景。

  import java.util.PriorityQueue;
  import java.util.Comparator;
  
  public class PriorityQueueConstructorDemo {
   public static void main(String[] args) {
       // 1. 使用默认构造函数（自然排序）
       PriorityQueue<String> defaultPq = new PriorityQueue<>();
  
       // 2. 指定初始容量与自定义降序比较器
       PriorityQueue<Integer> customPq = new PriorityQueue<>(20, new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return Integer.compare(o2, o1); // 降序排列，构建大顶堆
           }
       });
  
       customPq.offer(15);
       customPq.offer(40);
       System.out.println("大顶堆队头元素: " + customPq.peek()); // 40
   }
  }

核心操作组

核心操作组:

• boolean offer()：(E e)，将指定的元素插入此优先级队列。如果元素为 null，则抛出 NullPointerException。

• E poll()：()，获取并移除此队列的头，如果此队列为空，则返回 null。整个过程引发堆重构。

• E peek()：()，获取但不移除此队列的头，如果此队列为空，则返回 null。

• boolean remove()：(Object o)，从此队列中移除指定元素的单个实例（如果存在）。涉及线性扫描定位与局部堆重建。

  import java.util.PriorityQueue;
  
  public class PriorityQueueOperationDemo {
   public static void main(String[] args) {
       PriorityQueue<Double> pq = new PriorityQueue<>();
  
       // 元素入队
       pq.offer(3.14);
       pq.offer(1.41);
       pq.offer(2.71);
  
       // 检索队头
       System.out.println("当前队头 (peek): " + pq.peek()); // 1.41
  
       // 移除指定非队头元素
       boolean isRemoved = pq.remove(2.71);
       System.out.println("移除元素 2.71 是否成功: " + isRemoved);
  
       // 元素出队
       System.out.println("出队 (poll): " + pq.poll()); // 1.41
       System.out.println("出队 (poll): " + pq.poll()); // 3.14
   }
  }

注意事项

注意事项:

1. 严禁插入 null 元素：PriorityQueue 强制要求对元素进行比较。由于 null 无法与任何对象进行 compareTo 或 compare 操作，因此插入 null 会直接抛出 NullPointerException。

2. 元素类型必须可比：存入队列的元素必须实现 java.lang.Comparable 接口，或者在创建队列时显式传入 Comparator。否则，在插入第二个元素触发堆化调整时，会抛出 ClassCastException。

3. 迭代器无序性：PriorityQueue 的 iterator() 方法返回的迭代器不保证以任何特定的顺序遍历元素。如果需要按优先级顺序遍历，必须使用循环配合 poll() 方法。

4. 动态扩容机制：当内部数组容量不足时，系统会自动执行扩容。若原有容量小于 64，则容量翻倍（oldCap + oldCap + 2）；若原有容量大于等于 64，则容量增加 50%（oldCap + (oldCap >> 1)）。

5. 变异风险：将元素存入 PriorityQueue 后，如果修改了元素中参与优先级比较的属性，队列不会自动重新调整堆结构。这会导致堆的内部契约被破坏，产生未定义的行为。

实战案例：医院急诊分诊系统

实战案例：医院急诊分诊系统:

以下案例模拟医院急诊室的分诊流转过程。患者根据病情的严重程度（红、黄、绿三级，红色危重度最高）被分配不同的权重值，分诊系统通过 PriorityQueue 确保病情最危重的患者能够优先获得救治。

import java.util.PriorityQueue;
import java.util.Queue;

public class EmergencyTriageSystem {

    // 内部类：病患数据模型
    public static class Patient implements Comparable<Patient> {
        private final String name;
        private final int severityLevel; // 严重等级：1-危急(红), 2-紧急(黄), 3-普通(绿)

        public Patient(String name, int severityLevel) {
            this.name = name;
            this.severityLevel = severityLevel;
        }

        public String getName() {
            return name;
        }

        public int getSeverityLevel() {
            return severityLevel;
        }

        // 实现 Comparable 接口，定义优先级判定逻辑
        @Override
        public int compareTo(Patient o) {
            // 严重等级数字越小，权重越高，优先出队
            return Integer.compare(this.severityLevel, o.severityLevel);
        }

        @Override
        public String toString() {
            String label = switch (severityLevel) {
                case 1 -> "【红灯-危急】";
                case 2 -> "【黄灯-紧急】";
                default -> "【绿灯-普通】";
            };
            return label + " 患者: " + name;
        }
    }

    public static void main(String[] args) {
        // 初始化分诊队列（利用内部天然的可比性）
        Queue<Patient> triageQueue = new PriorityQueue<>();

        System.out.println("===== 阶段 1: 急诊患者陆续前来就诊 =====");
        triageQueue.offer(new Patient("张三", 3)); // 普通感冒
        triageQueue.offer(new Patient("李四", 1)); // 突发心梗（最高优先级）
        triageQueue.offer(new Patient("王五", 2)); // 骨折
        triageQueue.offer(new Patient("赵六", 1)); // 严重外伤（同高优先级）

        System.out.println("\n===== 阶段 2: 医生根据优先级依次接诊 =====");
        while (!triageQueue.isEmpty()) {
            // 自动筛选出当前队列中 severityLevel 最小的患者
            Patient currentPatient = triageQueue.poll();
            processTreatment(currentPatient);
        }

        System.out.println("\n[系统提示] 当前候诊队列已清空。");
    }

    private static void processTreatment(Patient patient) {
        System.out.println("[接诊中] 正在为 " + patient.getName() + " 进行紧急救治，病情级别码: " + patient.getSeverityLevel());
    }
}

Deque~

概述与体系结构

概述与体系结构:

java.util.Deque（Double Ended Queue，双端队列）是 Java 集合框架中的核心接口之一，继承自 java.util.Queue。双端队列支持在队首（Head）和队尾（Tail）同时进行高效的插入、删除和检查操作。

由于这种双向操作的特性，Deque 既可以作为先进先出（FIFO）的普通队列使用，也可以作为后进先出（LIFO）的栈（Stack）结构使用。Java 官方明确建议使用 Deque 代替传统的 java.util.Stack 类。

核心原理与方法体系

核心原理与方法体系:

Deque 接口针对队首和队尾的操作，分别提供了两套方法体系：一套在操作失败时抛出异常，另一套在操作失败时返回特殊值（null 或 false）。

方法对照矩阵

方法对照矩阵:

操作类型	队首（Head）- 抛出异常	队首（Head）- 返回特殊值	队尾（Tail）- 抛出异常	队尾（Tail）- 返回特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
移除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

API：Deque

队首操作组

队首操作组:

• void addFirst()：(E e)，将指定元素插入当前双端队列的队首。如果由于容量限制导致插入失败，则抛出 IllegalStateException。

• boolean offerFirst()：(E e)，将指定元素插入当前双端队列的队首。如果由于容量限制导致插入失败，则返回 false。

• E removeFirst()：()，检索并删除当前双端队列的队首元素。如果队列为空，则抛出 NoSuchElementException。

• E pollFirst()：()，检索并删除当前双端队列的队首元素。如果队列为空，则返回 null。

• E getFirst()：()，检索但不删除当前双端队列的队首元素。如果队列为空，则抛出 NoSuchElementException。

• E peekFirst()：()，检索但不删除当前双端队列的队首元素。如果队列为空，则返回 null。

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class DequeHeadDemo {
   public static void main(String[] args) {
       Deque<String> deque = new ArrayDeque<>();
  
       // 队首插入
       deque.addFirst("Element_1");
       deque.offerFirst("Element_2"); // 当前结构: [Element_2, Element_1]
  
       // 队首检查
       System.out.println("getFirst: " + deque.getFirst());
       System.out.println("peekFirst: " + deque.peekFirst());
  
       // 队首移除
       System.out.println("pollFirst: " + deque.pollFirst());
       System.out.println("removeFirst: " + deque.removeFirst());
   }
  }

队尾操作组

队尾操作组:

• void addLast()：(E e)，将指定元素插入当前双端队列的队尾。如果由于容量限制导致插入失败，则抛出 IllegalStateException。

• boolean offerLast()：(E e)，将指定元素插入当前双端队列的队尾。如果由于容量限制导致插入失败，则返回 false。

• E removeLast()：()，检索并删除当前双端队列的队尾元素。如果队列为空，则抛出 NoSuchElementException。

• E pollLast()：()，检索并删除当前双端队列的队尾元素。如果队列为空，则返回 null。

• E getLast()：()，检索但不删除当前双端队列的队尾元素。如果队列为空，则抛出 NoSuchElementException。

• E peekLast()：()，检索但不删除当前双端队列的队尾元素。如果队列为空，则返回 null。

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class DequeTailDemo {
   public static void main(String[] args) {
       Deque<String> deque = new ArrayDeque<>();
  
       // 队尾插入
       deque.addLast("Tail_1");
       deque.offerLast("Tail_2"); // 当前结构: [Tail_1, Tail_2]
  
       // 队尾检查
       System.out.println("getLast: " + deque.getLast());
       System.out.println("peekLast: " + deque.peekLast());
  
       // 队尾移除
       System.out.println("pollLast: " + deque.pollLast());
       System.out.println("removeLast: " + deque.removeLast());
   }
  }

栈操作等价组

栈操作等价组:

• void push()：(E e)，将元素推入当前双端队列所表示的栈顶（即队首）。等价于 addFirst(e)。

• E pop()：()，从当前双端队列所表示的栈顶（即队首）弹出一个元素。等价于 removeFirst()。

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class DequeStackDemo {
   public static void main(String[] args) {
       Deque<String> stack = new ArrayDeque<>();
  
       // 压栈操作 (LIFO)
       stack.push("Page_1");
       stack.push("Page_2");
       stack.push("Page_3"); // 栈顶
  
       // 查看栈顶元素
       System.out.println("当前栈顶: " + stack.peek()); // Page_3
  
       // 出栈操作
       while (!stack.isEmpty()) {
           System.out.println("弹出栈顶: " + stack.pop());
       }
   }
  }

注意事项

注意事项:

1. 严禁插入 null 元素：ArrayDeque 明确禁止插入 null 元素（会直接抛出 NullPointerException）。虽然 LinkedList 允许插入 null，但这属于严重的不良实践，因为 poll()、peek() 等方法返回 null 表示队列为空，混入 null 会导致业务逻辑无法准确判断状态。

2. 弃用 java.util.Stack 类：传统的 Stack 类继承自 Vector，所有操作均带有 synchronized 同步锁，性能低。此外，其继承关系破坏了封装性（暴露了按索引修改的方法）。在单线程环境下，必须优先选择 ArrayDeque 作为栈的替代实现。

3. 并发安全问题：ArrayDeque 和 LinkedList 都不是线程安全的。若在多线程环境下无同步地修改双端队列，会引发不可预期的行为或抛出 ConcurrentModificationException。并发场景下应使用 java.util.concurrent.LinkedBlockingDeque。

实战：文本编辑器管理器

实战案例：文本编辑器的撤销/重做（Undo/Redo）管理器:

以下案例利用 Deque 同时实现了栈（LIFO）与双端特性，构建了一个适合初学者理解的、可直接运行的编辑器历史记录控制组件。

import java.util.ArrayDeque;
import java.util.Deque;

public class EditorHistoryManager {

    // 撤销栈：存储可以被撤销的操作
    private final Deque<String> undoStack = new ArrayDeque<>();
    // 重做栈：存储可以被重做的操作
    private final Deque<String> redoStack = new ArrayDeque<>();

    // 限制历史记录的最大深度，防止内存溢出
    private final int maxHistorySize;

    public EditorHistoryManager(int maxHistorySize) {
        this.maxHistorySize = maxHistorySize;
    }

    /**
     * 执行新操作
     */
    public void executeAction(String action) {
        // 有新操作时，清空重做历史
        redoStack.clear();

        // 如果撤销栈达到最大深度，从队尾（最老的操作）移除
        if (undoStack.size() >= maxHistorySize) {
            String obsoleteAction = undoStack.pollLast();
            System.out.println("[内存优化] 废弃历史中最老的操作: " + obsoleteAction);
        }

        // 将新操作压入栈顶（队首）
        undoStack.push(action);
        System.out.println("[输入成功] 执行操作: " + action);
    }

    /**
     * 触发撤销（Undo）
     */
    public void undo() {
        if (undoStack.isEmpty()) {
            System.out.println("[警告] 没有可撤销的操作");
            return;
        }
        // 弹出当前最新操作，并转移至重做栈
        String currentAction = undoStack.pop();
        redoStack.push(currentAction);
        System.out.println("[撤销成功] 恢复至操作之前的状态。已撤销: " + currentAction);
    }

    /**
     * 触发重做（Redo）
     */
    public void redo() {
        if (redoStack.isEmpty()) {
            System.out.println("[警告] 没有可重做的操作");
            return;
        }
        // 从重做栈弹出，重新压入撤销栈
        String restoredAction = redoStack.pop();
        undoStack.push(restoredAction);
        System.out.println("[重做成功] 重新应用操作: " + restoredAction);
    }

    /**
     * 打印当前历史状态
     */
    public void printStatus() {
        System.out.println("---- 当前状态 ----");
        System.out.println("撤销栈(最新在左): " + undoStack);
        System.out.println("重做栈(最新在左): " + redoStack);
        System.out.println("-----------------");
    }

    public static void main(String[] args) {
        // 初始化一个最大历史深度为 3 的历史管理器
        EditorHistoryManager manager = new EditorHistoryManager(3);

        System.out.println("===== 场景 1: 连续输入与历史容量超限保护 =====");
        manager.executeAction("插入文本 'Hello'");
        manager.executeAction("修改字体为 'Arial'");
        manager.executeAction("插入图片 'logo.png'");
        manager.printStatus();

        // 触发超限淘汰机制
        manager.executeAction("加粗文本");
        manager.printStatus();

        System.out.println("\n===== 场景 2: 撤销与重做流转 =====");
        manager.undo(); // 撤销 加粗文本
        manager.undo(); // 撤销 插入图片
        manager.printStatus();

        manager.redo(); // 重做 插入图片
        manager.printStatus();
    }
}

DeQue-ArrayDeque

概述与体系结构

概述与体系结构:

java.util.ArrayDeque 是 Java 集合框架中基于可变长循环数组实现的双端队列（Double-Ended Queue）。它同时实现了 java.util.Deque 接口，继承自 java.util.AbstractCollection。

ArrayDeque 在设计上没有容量限制，可根据需求动态扩容。由于其底层采用连续内存布局的数组结构，无论是在作为栈（Stack）使用时（替代 java.util.Stack），还是作为FIFO 队列（Queue）使用时（替代 java.util.LinkedList），其性能和内存效率普遍优于链表结构。

核心原理

核心原理:

ArrayDeque 的高效性能源于其内部的循环数组（Circular Array）设计与双指针（Head & Tail）的位移机制。

循环双端缓冲区实现

循环双端缓冲区实现:

• 双指针机制：内部维护两个整型指针：head（指向队首元素所在位置）和 tail（指向队尾下一个即将插入元素的空槽）。
• 回绕逻辑（Wrapping）：由于采用循环结构，当 head 或 tail 移动到数组边界之外时，它们会自动回绕到数组的另一端。例如，在队首插入元素时，head 指针向左移动；若 head 减至 0 以下，则自动回绕至数组的末尾槽位。
• 扩容时机：当 head == tail 时，表明当前数组空间已被完全填满。此时 ArrayDeque 会触发自动扩容，申请一个通常为原容量 2 倍的新数组，并将原数组中的元素按照从 head 到 tail 的逻辑顺序重新复制到新数组中。

算法时间复杂度

算法时间复杂度:

• 两端插入/删除 (addFirst, pollLast 等)：均摊时间复杂度为 $O(1)$。
• 两端检查 (peekFirst, peekLast)：时间复杂度为 $O(1)$。
• 按索引或对象查找/删除 (remove(Object), contains)：需要线性扫描数组，时间复杂度为 $O(n)$。

API：ArrayDeque

构造方法组

构造方法组:

• ArrayDeque ArrayDeque()：()，创建一个默认初始容量（16）的空双端队列。

• ArrayDeque ArrayDeque()：(int numElements)，创建一个能够容纳指定数量元素的双端队列。系统会自动调整内部数组的实际大小以优化性能。

  import java.util.ArrayDeque;
  
  public class ArrayDequeConstructorDemo {
   public static void main(String[] args) {
       // 1. 默认构造
       ArrayDeque<String> defaultDeque = new ArrayDeque<>();
  
       // 2. 指定预估容量构造
       ArrayDeque<Integer> customDeque = new ArrayDeque<>(100);
  
       System.out.println("Default Size: " + defaultDeque.size());
       System.out.println("Custom Size: " + customDeque.size());
   }
  }

队首操作组

队首操作组:

• void addFirst()：(E e)，将指定元素插入到双端队列的队首。如果元素为 null，则抛出 NullPointerException。

• boolean offerFirst()：(E e)，将指定元素插入到双端队列的队首。由于 ArrayDeque 是无界的，该方法在正常情况下永远返回 true。

• E removeFirst()：()，检索并删除当前双端队列的队首元素。如果队列为空，则抛出 NoSuchElementException。

• E pollFirst()：()，检索并删除当前双端队列的队首元素。如果队列为空，则返回 null。

• E getFirst()：()，检索但不删除当前双端队列的队首元素。如果队列为空，则抛出 NoSuchElementException。

• E peekFirst()：()，检索但不删除当前双端队列的队首元素。如果队列为空，则返回 null。

  import java.util.ArrayDeque;
  
  public class ArrayDequeHeadDemo {
   public static void main(String[] args) {
       ArrayDeque<String> deque = new ArrayDeque<>();
  
       // 队首插入
       deque.addFirst("Node_A");
       deque.offerFirst("Node_B"); // 当前物理/逻辑顺序: [Node_B, Node_A]
  
       // 队首检查
       System.out.println("Peek First: " + deque.peekFirst()); // Node_B
  
       // 队首出队
       System.out.println("Poll First: " + deque.pollFirst()); // Node_B
       System.out.println("Remove First: " + deque.removeFirst()); // Node_A
   }
  }

队尾操作组

队尾操作组:

• void addLast()：(E e)，将指定元素插入到双端队列的队尾。

• boolean offerLast():: (E e)，将指定元素插入到双端队列的队尾。

• E removeLast()：()，检索并删除当前双端队列的队尾元素。如果队列为空，则抛出 NoSuchElementException。

• E pollLast()：()，检索并删除当前双端队列的队尾元素。如果队列为空，则返回 null。

• E getLast()：()，检索但不删除当前双端队列的队尾元素。如果队列为空，则抛出 NoSuchElementException。

• E peekLast()：()，检索但不删除当前双端队列的队尾元素。如果队列为空，则返回 null。

  import java.util.ArrayDeque;
  
  public class ArrayDequeTailDemo {
   public static void main(String[] args) {
       ArrayDeque<Integer> deque = new ArrayDeque<>();
  
       // 队尾插入
       deque.addLast(100);
       deque.offerLast(200);
  
       // 队尾检查
       System.out.println("Peek Last: " + deque.peekLast()); // 200
  
       // 队尾出队
       System.out.println("Poll Last: " + deque.pollLast()); // 200
       System.out.println("Poll Last: " + deque.pollLast()); // 100
   }
  }

栈操作等价组

栈操作等价组:

• void push()：(E e)，将元素推入双端队列所表示的栈顶（即队首）。等价于 addFirst(e)。

• E pop()：()，从双端队列所表示的栈顶（即队首）弹出一个元素。等价于 removeFirst()。

  import java.util.ArrayDeque;
  
  public class ArrayDequeStackDemo {
   public static void main(String[] args) {
       ArrayDeque<String> stack = new ArrayDeque<>();
  
       // 压栈
       stack.push("Command_1");
       stack.push("Command_2");
  
       // 出栈
       while (!stack.isEmpty()) {
           System.out.println("Pop Stack: " + stack.pop());
       }
   }
  }

注意事项

1. 严禁插入 null 元素：ArrayDeque 显式拒绝任何 null 元素的插入尝试。若传入 null，会立即抛出 NullPointerException。这是为了确保 poll()、peek() 等方法返回 null 时，能够无歧义地代表“队列当前为空”。

2. 非线程安全：ArrayDeque 没有内置的线程同步机制。在多线程环境中，若至少有一个线程对其进行结构性修改，则必须在外部实施同步控制。常见的做法是使用 java.util.Collections.synchronizedDeque() 进行包装，或者改用并发包下的 java.util.concurrent.LinkedBlockingDeque。

3. 快速失败（Fail-Fast）迭代器：由该类的 iterator() 方法返回的迭代器是快速失败的。在迭代器创建之后，如果队列在非迭代器自身方法外被修改（如同线程并发修改或多线程修改），迭代器将尽最大努力抛出 ConcurrentModificationException。

4. 内存局部性优势：相比于 LinkedList，ArrayDeque 的底层数组在物理内存上是连续分配的。这意味着它具有更好的 CPU 缓存命中率（Cache Locality），且避免了 LinkedList 为每个节点创建 Node 对象所带来的额外内存开销与频繁的 GC 压力。

实战：浏览器历史记录导航

以下案例利用 ArrayDeque 的双端队列特性，模拟现代浏览器中的“前进”与“后退”功能。系统使用两个 ArrayDeque 实例分别作为后退栈和前进栈，从而实现高效的页面状态流转。

import java.util.ArrayDeque;
import java.util.Deque;

public class BrowserNavigationSimulator {

    // 后退栈：存放当前页面之前的历史记录
    private final Deque<String> backStack = new ArrayDeque<>();
    // 前进栈：存放执行了“后退”操作后，可以再次“前进”的历史记录
    private final Deque<String> forwardStack = new ArrayDeque<>();
    // 当前正在访问的页面
    private String currentPage;

    public BrowserNavigationSimulator(String homePage) {
        this.currentPage = homePage;
        System.out.println("[主页初始化] 进入门户: " + currentPage);
    }

    /**
     * 用户点击超链接，访问新页面
     */
    public void visit(String newPage) {
        if (currentPage != null) {
            // 将当前页面压入后退栈
            backStack.push(currentPage);
        }
        // 访问新页面时，必须清空前进栈
        forwardStack.clear();
        currentPage = newPage;
        System.out.println("[访问新页] 跳转至 -> " + currentPage);
    }

    /**
     * 用户点击“后退”按钮
     */
    public void goBack() {
        if (backStack.isEmpty()) {
            System.out.println("[无法后退] 当前已是最早的历史记录。");
            return;
        }
        // 将当前页面压入前进栈
        forwardStack.push(currentPage);
        // 从后退栈弹出上一页作为当前页
        currentPage = backStack.pop();
        System.out.println("[执行后退] 返回至 <- " + currentPage);
    }

    /**
     * 用户点击“前进”按钮
     */
    public void goForward() {
        if (forwardStack.isEmpty()) {
            System.out.println("[无法前进] 当前已是最新的网页。");
            return;
        }
        // 将当前页面压入后退栈
        backStack.push(currentPage);
        // 从前进栈弹出下一页作为当前页
        currentPage = forwardStack.pop();
        System.out.println("[执行前进] 推进至 -> " + currentPage);
    }

    /**
     * 打印当前导航器的状态
     */
    public void printStatus() {
        System.out.println("  ├─ 历史后退栈: " + backStack);
        System.out.println("  ├─ 当前活动页: [" + currentPage + "]");
        System.out.println("  └─ 历史前进栈: " + forwardStack);
        System.out.println();
    }

    public static void main(String[] args) {
        // 初始化浏览器，默认打开百度
        BrowserNavigationSimulator browser = new BrowserNavigationSimulator("baidu.com");
        browser.printStatus();

        // 1. 模拟用户连续点击网页
        System.out.println("===== 场景 1: 用户连续浏览网页 =====");
        browser.visit("news.baidu.com");
        browser.visit("github.com");
        browser.visit("stackoverflow.com");
        browser.printStatus();

        // 2. 模拟用户连续点击后退
        System.out.println("===== 场景 2: 用户连续点击后退 =====");
        browser.goBack(); // 回到 github.com
        browser.goBack(); // 回到 news.baidu.com
        browser.printStatus();

        // 3. 模拟用户点击前进，随后又访问了第三方新页面
        System.out.println("===== 场景 3: 点击前进后，突发访问新页面 =====");
        browser.goForward(); // 前进到 github.com
        browser.visit("oracle.com"); // 访问新站，此时前进栈应被自动清空
        browser.printStatus();

        // 4. 再次尝试前进
        System.out.println("===== 场景 4: 尝试在无前进历史下点击前进 =====");
        browser.goForward();
    }
}